Categorie archieven: Getaltheorie

De kleine stelling van Fermat

Geplaatst op door

Als p een priemgetal is en a en p onderling ondeelbaar zijn dan geldt:

    \[a^{p-1} \equiv 1 \text{ mod } p\]

Uit deze stelling, die de kleine stelling van Fermat genoemd wordt en in 1640 een eerste keer vermeld werd, volgt dat voor elke a en voor een priemgetal p geldt dat

    \[a^p \equiv a \text { mod } p\]

De stelling wordt bijvoorbeeld gebruikt om de restklasse modulo een groot getal uit te rekenen. Bereken bijvoorbeeld de rest bij deling van 2^{245} door 11. Volgens de kleine stelling van Fermat is 2^{10} \equiv 1 \text{ mod } 11, dus is 2^{245} \equiv (2^{10})^24.2^5 \equiv 2^5 \equiv 10 \text{ mod } 11.

Er bestaat een veralgemening voor de stelling, die zegt dat als a en m onderling ondeelbaar zijn, geldt

    \[a^{\varphi(m)} \equiv 1 \text { mod }m\]

Hierbij is \varphi(m) de totiënt functie van Euler die het aantal getallen, kleiner dan m, berekent die onderling ondeelbaar zijn met m. Deze stelling wordt de Euler-Fermat stelling genoemd.

Deelbaarheid door 3, 7, 9 en 11

Geplaatst op door

Iedereen weet dat een getal deelbaar is door 2 als het laatste cijfer, in zijn decimale notatie, even is.  Want een getal n kan je schrijven als n=10k+u, waarbij u het laatste cijfer is in de decimale notatie van n. Het is duidelijk dat 2|n als en slechts als 2|u. Hetzelfde geldt voor 5.

Elk getal n  is te schrijven  als n=100k+u, waarbij u het getal is gevormd door de laatste 2 cijfers van n. Bijgevolg is n deelbaar door 4 of 25 als de laatste 2 cijferss deelbaar zijn door 4 of 25.

Hoe kunnen we nu zien of een getal deelbaar is door 3, 9 of 11? Bekijken we eerst een stelling over congruenties met veeltermen met gehele cëfficiënten:

Stel f(x)=\sum_{k=0}^nc_kx^k met c_i \in \mathbb{Z}. Als a \equiv b mod m, dan is f(a) \equiv f(b) mod m.

Neem nu a=\sum_{k=0}^na_k10^k, de decimale schrijfwijze van het getal a en noteer s=\sum_{k=0}^na_k en t=\sum_{k=0}^n(-1)^ka_k. Het is duidelijk dat a=f(10) met f(x)=\sum_{k=0}^na_kx^k en dat s=f(1). Omdat 10 \equiv 1 mod 9, geldt volgens vorige stelling dat f(10) \equiv f(1) mod 9 of met andere woorden : een getal is deelbaar door 9 als de som van haar cijfers deelbaar is door 9. Analoog voor deelbaarheid door 3. Het bewijs voor deelbaarheid door 11 volgt uit het feit dat 10 \equiv -1 mod 11 en t=f(-1).

Besluit:
Een getal is deelbaar door 3 of 9 als de som van de cijfers van het getal deelbaar is door 3 of 9.
Een getal is deelbaar door 11 als t=\sum_{k=0}^n(-1)^ka_k deelbaar is door 11.

 

Een toemaatje : deelbaarheid door 7: Omdat 10^3 \equiv -1 mod 7 kan je  deelbaarheid door 7 als volgt vinden: Verdeel het getal van rechts naar links in groepjes van 3. Voor zie elk groepje alternerend met een + en – teken. Een getal is deelbaar door 7 las de som van die getallen deelbaar is door 7. Zo is bijvoorbeeld  2 345 678 902 deelbaar door 7 omdat 902 -678 + 345 – 2 = 567 en dat is deelbaar door 7 .

De Euler-phi functie

Geplaatst op door

De Euler-phi functie, ook wel totiënt functie of indicator genoemd, telt het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n, die onderling ondeelbaar zijn met n. Notatie: \varphi(n).

Zo is bijvoorbeeld \varphi(10)=4, want de enige getallen die onderling ondeelbaar zijn met 10 en kleiner zijn dan 10, zijn 1,3,7 en 9.

Enkele eigenschappen:

  • \varphi(1)=1.
  • Als p een priemgetal is dan is \varphi(p)=p-1.
  • Als p een priemgetal is dan is \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).
  • Als n=p_1^{k_1}.p_2^{k_2}.\cdots.p_r^{k_r} de priemontbinding is van n, dan geldt \varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1). Dit kan je ook schrijven als :

        \[\varphi(n)= n.\prod_{p|n}(1-\frac{1}{p})\]

    Hierbij doorloopt p alle priemdelers van n.

  • \sum_{d|n}\varphi(d)=n
  • De indicator geeft ook de omvang aan van de multiplicatieve groep van natuurlijke getallen modulo n

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}\}\]