Kongruens modulo
100 / 7 = 14 rest 2
Hvis man kun er interesseret i, hvad resten bliver, siger matematikeren: ”100 er kongruent med 2 modulus 7”. Det skrives i kort notation således:
100 ≡ 2 mod 7
Hvis vi nu prøver at se på dette med hensyn til kubiktal, får vi følgende:
1³ ≡ 1 mod 3
2³ ≡ 2 mod 3
3³ ≡ 0 mod 3
4³ ≡ 1 mod 3
5³ ≡ 2 mod 3
6³ ≡ 0 mod 3
7³ ≡ 1 mod 3
osv.
Det vil fortsætte i den samme simple ring i det uendelige. Før eventuelt bevis derfor.
Vi prøver nu det samme med femte potens modulus 5:
1^5 ≡ 1 mod 5
2^5 ≡ 2 mod 5
3^5 ≡ 3 mod 5
4^5 ≡ 4 mod 5
5^5 ≡ 0 mod 5
6^5 ≡ 1 mod 5
…
Akkurat samme mønster. Men hvad med 7?
1^7 ≡ 1 mod 7
2^7 ≡ 2 mod 7
3^7 ≡ 3 mod 7
…
Intet nyt. Så 9 da?
1^9 ≡ 1 mod 9
2^9 ≡ 8 mod 9
3^9 ≡ 0 mod 9
4^9 ≡ 1 mod 9
5^9 ≡ 8 mod 9
…
Her brydes systemet. Og vi kan konkludere, at: [m^n ≡ m mod n] kun er gyldigt, dersom n er et primtal.
Det er alt sammen ikke så overraskende endda. Se blot følgende:
2^1 ≡ 2 mod 5
2^2 ≡ 4 mod 5
2^3 ≡ 3 mod 5
2^4 ≡ 1 mod 5
2^5 ≡ 2 mod 5
2^6 ≡ 4 mod 5
2^7 ≡ 3 mod 5
2^8 ≡ 1 mod 5
2^9 ≡ 2 mod 5
…
Også på denne måde kører det i ring, og af gode grunde vil det aldrig give kongruens nul.
2^1 ≡ 2 mod 7
2^2 ≡ 4 mod 7
2^3 ≡ 1 mod 7
2^4 ≡ 2 mod 7
2^5 ≡ 4 mod 7
2^6 ≡ 1 mod 7
2^7 ≡ 2 mod 7
…
Men som du ser her, så kan det i visse situationer ske, at ringen kun går gennem halvdelen af de mulige (3, 5 og 6 optræder ikke). Det betyder så blot, at 2 optræder en ekstra gang forinden potens 7, nemlig ved potens 4.
Reglen er den, at hvis 2n+1 er et primtal, så løber den gennem alle tal. Hvis ikke, så ikke. Altså 5*2+1=11. Da 11 er et primtal, så kommer alle tal fra 1 til 4 med. Men 7*2+1=15, der ikke er primtal. Derfor får man kun halvdelen af tallene fra 1 til 6 med i dette tilfælde.
Det blev første bevist i år 1803 af pariserinden Anne-Sophie Germain.
Hvis man kun er interesseret i, hvad resten bliver, siger matematikeren: ”100 er kongruent med 2 modulus 7”. Det skrives i kort notation således:
100 ≡ 2 mod 7
Hvis vi nu prøver at se på dette med hensyn til kubiktal, får vi følgende:
1³ ≡ 1 mod 3
2³ ≡ 2 mod 3
3³ ≡ 0 mod 3
4³ ≡ 1 mod 3
5³ ≡ 2 mod 3
6³ ≡ 0 mod 3
7³ ≡ 1 mod 3
osv.
Det vil fortsætte i den samme simple ring i det uendelige. Før eventuelt bevis derfor.
Vi prøver nu det samme med femte potens modulus 5:
1^5 ≡ 1 mod 5
2^5 ≡ 2 mod 5
3^5 ≡ 3 mod 5
4^5 ≡ 4 mod 5
5^5 ≡ 0 mod 5
6^5 ≡ 1 mod 5
…
Akkurat samme mønster. Men hvad med 7?
1^7 ≡ 1 mod 7
2^7 ≡ 2 mod 7
3^7 ≡ 3 mod 7
…
Intet nyt. Så 9 da?
1^9 ≡ 1 mod 9
2^9 ≡ 8 mod 9
3^9 ≡ 0 mod 9
4^9 ≡ 1 mod 9
5^9 ≡ 8 mod 9
…
Her brydes systemet. Og vi kan konkludere, at: [m^n ≡ m mod n] kun er gyldigt, dersom n er et primtal.
Det er alt sammen ikke så overraskende endda. Se blot følgende:
2^1 ≡ 2 mod 5
2^2 ≡ 4 mod 5
2^3 ≡ 3 mod 5
2^4 ≡ 1 mod 5
2^5 ≡ 2 mod 5
2^6 ≡ 4 mod 5
2^7 ≡ 3 mod 5
2^8 ≡ 1 mod 5
2^9 ≡ 2 mod 5
…
Også på denne måde kører det i ring, og af gode grunde vil det aldrig give kongruens nul.
2^1 ≡ 2 mod 7
2^2 ≡ 4 mod 7
2^3 ≡ 1 mod 7
2^4 ≡ 2 mod 7
2^5 ≡ 4 mod 7
2^6 ≡ 1 mod 7
2^7 ≡ 2 mod 7
…
Men som du ser her, så kan det i visse situationer ske, at ringen kun går gennem halvdelen af de mulige (3, 5 og 6 optræder ikke). Det betyder så blot, at 2 optræder en ekstra gang forinden potens 7, nemlig ved potens 4.
Reglen er den, at hvis 2n+1 er et primtal, så løber den gennem alle tal. Hvis ikke, så ikke. Altså 5*2+1=11. Da 11 er et primtal, så kommer alle tal fra 1 til 4 med. Men 7*2+1=15, der ikke er primtal. Derfor får man kun halvdelen af tallene fra 1 til 6 med i dette tilfælde.
Det blev første bevist i år 1803 af pariserinden Anne-Sophie Germain.