Categorie archieven: Getaltheorie

De Chinese reststelling

Geplaatst op door

Naast lineaire congruenties , kan je ook werken met stelsels van lineaire congruenties. Zoals bijvoorbeeld:

Volgens de Chinese reststelling geldt dan: Als elke a_i en m_i onderling ondeelbaar zijn en als alle m_i twee aan twee onderling ondeelbaar zijn, dan heeft dit stelsel een unieke oplossing modulo m_1.m_2.\cdots.m_n.

Los op:
\begin{cases} x\equiv 2 \text{ mod }5 \\3x\equiv 1 \text{ mod }8 \end{cases} of  \begin{cases} x\equiv 2 \text{ mod }5 \\x\equiv 3 \text{ mod }8 \end{cases}

Dit betekent dat x=2+5k=3+8l. Dus 5k \equiv 1 \text{ mod } 8 of k \equiv 5 \text{ mod } 8. Hieruit volgt dat k=5+8p en dus is x=2+5(5+8p)=27+40p.

De unieke oplossing van het gegeven stelsel is x=27 \text{ mod } 40.

Lineaire congruenties

Geplaatst op door

Naast lineaire vergelijkingen , kunnen we ook lineaire congruenties bekijken:

    \[ax \equiv b \text{ mod } m \text{ met } a,b,m\in \mathbb{Z}\]

Hier is de vraag of er een gehele x te vinden is zodat  ax-b deelbaar is door m. Het is duidelijk dat als x_0 een oplossing is, dan zijn alle getallen uit de restklasse x_0 \text{ mod } m ook oplossingen. De oplossingsverzameling verandert ook niet als we a en b veranderen in andere getallen uit hun restklasse mod m. Onder een oplossing van een lineaire congruentie verstaat men dus een restklesse mod m.

  • Wanneer is een congruentie oplosbaar?  Dat is zo als en slechts als de grootste gemene deler van a en m een deler is van b. Als a en m onderling ondeelbaar zijn, bestaat het inverse element van a mod m en is dus x=a^{-1}b \text{ mod } m. Als de grootste gemene deler d van a en m niet 1 is , dan delen we eerst door d en dan krijgen we vorige situatie.
  • In het geval dat ggd(a,m) = 1 hebben we een unieke oplossing. Als echter ggd(a,m) = d , dan hebben we d oplossingen. We krijgen immers 1 oplossing mod \frac{m}{d} en deze geeft precies volgende verschillende restklassen mod m: x_0, x_0+\frac{m}{d},x_0+2\frac{m}{d},\cdots, x_0+(d-1)\frac{m}{d}.

Los op : 6x \equiv 8 \text{ mod }10 .

  • Delen door de ggd(6,10) = 2 geeft 3x \equiv 4 \text{ mod } 5 .
  • Omdat 3.2 = 6 \equiv 1 \text{ mod } 5 is 3^{-1} =2
  • En dus is x\equiv 2.4 \equiv 3 \text{ mod } 5.
  • Alle oplossingen zijn dus de restklassen 3 en 8 modulo 10. De oplossingsverzameling is:

        \[\{3+10k, 8+10l \text{ met } k,l\in \mathbb{Z}\}\]

 

Multiplicatieve functies

Geplaatst op door

Een rekenkundige functie is een functie f:\mathbb{N} \longrightarrow \mathbb{C}. Een rekenkundige functie drukt een zekere eigenschap van de natuurlijke getallen uit. Een rekenkundige functie f is  multiplicatief  als voor elk tweetal onderling ondeelbare getallen m en n geldt dat

    \[f(m.n)=f(m).f(n)\]

Omdat elk natuurlijk getal ontbonden kan worden in priemfactoren, is een multiplicatieve functie gekend als je de beelden van de priemfactoren kent.

In volgende tekst worden enkele belangrijke multiplicatieve functies bestudeerd:

  • De functie die het aantal delers van een getal berekent.
  • De functie die de som berekent van alle delers van een getal.
  • De Möbius functie.
  • De Dirichlet functie.
  • De Euler functie die van een getal berekent hoeveel getallen er onderling ondeelbaar zijn met het getal.

De entier-functie

Geplaatst op door

Het grootste gehele getal kleiner dan of gelijk aan het reële getal x heet de entier ( frans voor ‘ geheel’) van x. Notatie: \lfloor x\rfloor. Deze notatie werd voor het eerst gebruikt door C.F.Gauss in 1808. Soms wordt ook de notatie G(x) gebruikt.

Zo is \lfloor 7,43 \rfloor = 7,  \lfloor -\pi \rfloor =-4 en \lfloor 2017 \rfloor =2017.

Een paar eigenschappen:

  • \lfloor x \rfloor = \text{ max } \{ m \in \mathbb{Z} : m \leq x \}.
  • \lfloor x \rfloor = m \Leftrightarrow x-1 < m \leq x \Leftrightarrow m \leq x <m+1.
  • Voor elk natuurlijk getal n geldt : \lfloor x+n \rfloor =\lfloor x \rfloor +n.
  • \lfloor x \rfloor +\lfloor y \rfloor \leq \lfloor x+y \rfloor \leq \lfloor x \rfloor+\lfloor y \rfloor+1.
  • Voor m \in \mathbb{N} en n \in \mathbb{Z} geldt: n= \lfloor \frac{n}{m} \rfloor+\lfloor \frac{n+1}{m} \rfloor+\cdots +\lfloor \frac{n+m-1}{m} \rfloor.
  • Voor m \in \mathbb{N} geldt: \lfloor mx \rfloor=\lfloor x \rfloor+\lfloor x +\frac{1}{m}\rfloor+\cdots+\lfloor x+\frac{m-1}{m} \rfloor.

Soms definieert men ook volgende functies:

  • Het kleinste geheel getal groter dan of gelijk aan x als \lceil x \rceil.
  • Het breukdeel van x als \{x\}=x-\lfloor x \rfloor. Het breukdeel wordt dikwijls bekeken als het deel na de komma, maar dat is slechts correct voor positieve getallen.

Stelling van Dirichlet voor rekenkundige rijen

Geplaatst op door

De Stelling van Dirichlet over rekenkundige rijen, ook bekend onder de naam Priemgetallenstelling van Dirichlet (Duits wiskundige, 1805-1859), is een stelling uit de getaltheorie die handelt over het voorkomen van priemgetallen in rekenkundige rijen.

De stelling luidt dat, als a en b onderling ondeelbaar zijn, dus hun grootste gemene deler gelijk is aan 1, de rij

{\displaystyle a,\ a+b,\ a+2b,\ a+3b,\ a+4b,\ \dots }

oneindig veel priemgetallen bevat. 

De stelling is een veralgemening van een bewering door Euler dat elke rekenkundige rij die met 1 begint oneindig veel priemgetallen bevat. De huidige vorm werd geformuleerd door Legendre en in 1837 bewezen door Johann Dirichlet.

De wiskundewereld heeft zich eigenlijk altijd al beziggehouden met het zoeken naar formules van rijen die oneindig veel priemgetallen bevatten.