Tag archieven: modulo rekenen

Op welk cijfer eindigt…

Geplaatst op door

Wat is de rest bij deling door 10 van het 2022ste getal in de rij  

    \[3,3^3,3^{3^3},...\]

  • De gegeven rij kan ook gegeven worden door middel van een recursief voorschrift: t_1=3 en t_{n+1}=3^{t_n}.

  • Berekenen we een paar termen van de rij: 3 , 27 , 7625597484987. We zien dat ze zeer snel toenemen in grootte, maar we hebben wel al 2 keer een 7 achteraan. Zou dat een patroon zijn?

  • Elke term is een viervoud plus 3, want t_n=(4 voud -1)^{t_{n-1}} en omdat elke term in de rij oneven is is t_n dus een 4voud min 1, of met anders geformuleerd : een drievoud plus 3.

  • Dan is t_{n+1}=3^{4v+3}=3^3.3^{4v}=27.81^v.
  • Werken we nu modulo 10: t_{n+1}\equiv 7.1^v\equiv 7.
  • Dus elke term van de rij eindigt op 7, dus ook de 2022ste term.

De klok

Geplaatst op door

Kunnen de drie wijzers van een uurwerk onderling twee aan twee hoeken van 120 graden vormen?

  • Noteer het tijdstip als x. Dit is een reëel getal. De kleine wijzer staat dan op 30x mod 360. graden, want na 1 uur heeft deze wijzer 30 graden afgelegd. De grote wijzer staat dan op 360x mod 360 graden, vermits er 60 minuten in een uur zijn. Omdat er 60 seconden in een minuut zijn , zal tenslotte de secondewijzer op 21600x mod 360 graden staan.
  • Het vraagstuk herleidt zich tot een volgend stelsel (telkens mod 360 genomen):

        \[30x-360x=120\]

        \[360x-21600x=120\]

        \[21600x-30x=120\]

  • Het kan ook het volgende  stelsel geven:

        \[360x - 30x=120\]

        \[21600x-360x=120\]

        \[30x-21600x=120\]

  • We bespreken enkel het eerste stelsel; het tweede geval verloopt analoog.
  • Na vereenvoudiging krijgen we :

        \[x=\frac{4}{11}(\mod \frac{12}{11})\]

        \[x=\frac{1}{177}(\mod \frac{3}{177})\]

        \[x=\frac{8}{719}(\mod \frac{12}{719})\]

  • Dus

        \[x=\frac{4}{11}(1+3k)=\frac{1}{177}(1+3l)=\frac{4}{719}(2+3m)\]

  • Maar dan moet  

        \[4.177.719(1+3k)=11.719(1+3l)\]

  • Dis  is onmogelijk want het eerste lid is een drievoud en het tweede niet!
  • De drie wijzers kunnen dus nooit twee aan twee een hoek van 120 graden vormen.

Toepassingen op stelling van Fermat

Geplaatst op door

Nog even in herinnering brengen, de kleine stelling van Fermat luidt: Als p een priemgetal is Ena en p onderling ondeelbaar zijn dan is

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

 of

    \[a^p \equiv a \mod p\]

 

Nu een paar toepassingen:

  • n^{13}-n is altijd deelbaar door 2730. Bewijs.
    Spoiler

    • ]We weten dat 2730 = 2.3.5.7.13. Te bewijzen is dan dat n^{13}-n\equiv 0 \mod 2730.
    • Het volstaat dus te bewijzen dat de opgave deelbaar is door de priemfactoren 2,3,5,7,13.
    • En inderdaad n^{13}-n\equiv 0 \mod 2,3,5,7 en 13 met behulp van de stelling van Fermat



  • 5^p-2*3^p+1 is een p-voud als p priem is. Bewijs. 
    Spoiler
    • Modulo p is 5^p\equiv 5 en 3^p÷equiv 3
    • Dus is 5^p-2*3^p+1 \ 5-2*3+1\equiv 0:mod p.




  • 1492^n-1771^n-1863^n+2141^n is steeds deelbaar door 1946. Bewijs dit  en volgende opgaven zelf!
  • n ^2+2n+12 is nooit deelbaar door 112. Tip : vul alle waarden van n in modulo 7.
  • Als n oneven is, dan eindigt de decimale schrijfwijze van 2^{2n}(2^{2n+1}-1) steeds op 28.
  • Voor welke n is n^{n+1}+(n+1)^n een drievoud?

            

Stelling van Wilson

Geplaatst op door

De kleine stelling van Fermat zegt ons dat voor een priemgetal p geldt dat a^p \equiv a \mod{p}. Maar dan zijn 1,2, … , p – 1 allemaal nulpunten van de veelterm X^{p-1}-1 in de verzameling \mathbb{Z}_p[X] en dus kunnen we, omdat er geen nuldelers zijn, volgende ontbinding neerschrijven: X^{p-1}-1 = (X-1)(X-2) \cdots (X-(p-1)).
Door hierin X te vervangen door 0, vinden we een deel van volgende stelling:

    \[p \text{ is priem als en slechts als } (p-1)! \equiv -1 \mod{p}\]

Dit resultaat staat bekend als de stelling van Wilson, naar de Engelse wiskundige John Wilson (1741-1793). Nochtans komt dit resultaat een eerste keer voor bij Abu Ali al-Hasan ibn al-Haytham (965-1040)

Bovendien had Wilson geen bewijs van de stelling. Het was Lagrange die in 1771 het eerste bewijs ervan formuleerde.

Het is ook duidelijk dat als n een samengesteld getal is, groter dan 4,  dat  (n-1)! \equiv 0 \mod{n}.

Een algemene vorm is voor ieder oneven priemgetal p en voor ieder positief geheel getal k kleiner dan p:

    \[(k-1)!(p-k)! \equiv (-1)^k \mod{p}\]

Deze veralgemening danken we aan C.F.Gauss

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.