Delelighet og Euklids algoritme

Vi sier at \(a \mid b\) («\(a\) deler \(b\)») dersom det finnes et heltall \(k\) med \(b = ak\). Divisjonsalgoritmen sier at for \(a\) og \(d>0\) finnes entydige \(q,r\) med \(a = dq + r\) og \(0 \le r < d\). Den største felles divisoren \(\gcd(a,b)\) finnes effektivt med Euklids algoritme, som hviler på identiteten nedenfor.

Euklids algoritme: \(\gcd(a,b) = \gcd(b, a \bmod b)\). Gjenta til resten blir 0; siste ikke-null rest er \(\gcd(a,b)\).

gcd–lcm: \(\gcd(a,b)\cdot \operatorname{lcm}(a,b) = ab\).

Eksempel 1: Finn \(\gcd(252,198)\).

\(252 = 1\cdot 198 + 54\)

\(198 = 3\cdot 54 + 36\)

\(54 = 1\cdot 36 + 18\)

\(36 = 2\cdot 18 + 0\)

Siste ikke-null rest \(\Rightarrow \gcd(252,198) = 18\)

Utvidet Euklid, Bézout og modulær invers

Utvidet Euklid uttrykker \(\gcd(a,b)\) som en heltallskombinasjon \(sa + tb\) (Bézouts identitet). Dette gir oss direkte den modulære inversen: dersom \(\gcd(a,n)=1\), gir \(sa + tn = 1\) at \(sa \equiv 1 \pmod n\), altså \(a^{-1} \equiv s \pmod n\).

Modulær invers: \(a^{-1} \bmod n\) finnes \(\iff \gcd(a,n)=1\). Finn den med utvidet Euklid (bakoversubstitusjon).

RSA: \(N = pq\), \(\varphi(N) = (p-1)(q-1)\), velg \(e\) med \(\gcd(e,\varphi)=1\), finn \(d\) med \(de \equiv 1 \pmod{\varphi(N)}\).

Eksempel 2: Finn \(7^{-1} \bmod 26\).

\(26 = 3\cdot 7 + 5\)

\(7 = 1\cdot 5 + 2\)

\(5 = 2\cdot 2 + 1\)

\(1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7\)

\(= 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7\)

\(7^{-1} \equiv -11 \equiv 15 \pmod{26}\); kontroll: \(7\cdot 15 = 105 = 4\cdot 26 + 1\)

Kongruenser og lineære kongruenser

Skriv \(a \equiv b \pmod n\) når \(n \mid (a-b)\). Kongruens modulo \(n\) er en ekvivalensrelasjon (refleksiv, symmetrisk, transitiv) og bevarer addisjon, subtraksjon, multiplikasjon og potens. Divisjon krever invers eller kanselleringsregelen \(ac \equiv bc \Rightarrow a \equiv b \pmod{n/\gcd(c,n)}\).

Lineær kongruens: \(ax \equiv b \pmod n\) har løsning \(\iff d = \gcd(a,n)\) deler \(b\). Da finnes nøyaktig \(d\) løsninger modulo \(n\).

Store potenser: bruk Fermat \(a^{p-1} \equiv 1 \pmod p\) (\(p\) primtall, \(p\nmid a\)) til å redusere eksponenten.

Eksempel 3: Løs \(6x \equiv 4 \pmod{10}\).

\(d = \gcd(6,10) = 2\), og \(2 \mid 4\) \(\Rightarrow\) 2 løsninger

Del på 2: \(3x \equiv 2 \pmod 5\)

\(3^{-1} \equiv 2 \pmod 5\), så \(x \equiv 2\cdot 2 = 4 \pmod 5\)

Modulo 10: \(x \equiv 4\) og \(x \equiv 9\)

Kinesisk restteorem

Når modulene \(n_1,\dots,n_k\) er parvis innbyrdes primiske, har systemet \(x \equiv a_i \pmod{n_i}\) en entydig løsning modulo \(N = \prod n_i\).

CRT-formel: \(x \equiv \sum_i a_i M_i y_i \pmod N\), der \(M_i = N/n_i\) og \(y_i \equiv M_i^{-1} \pmod{n_i}\).

Eksempel 4: \(x \equiv 2\,(3),\ x \equiv 3\,(5),\ x \equiv 2\,(7)\).

\(N = 105\); \(M_1 = 35, M_2 = 21, M_3 = 15\)

\(35 \equiv 2 \pmod 3 \Rightarrow y_1 = 2\); \(21 \equiv 1 \pmod 5 \Rightarrow y_2 = 1\); \(15 \equiv 1 \pmod 7 \Rightarrow y_3 = 1\)

\(x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140 + 63 + 30 = 233\)

\(x \equiv 233 \equiv 23 \pmod{105}\)

Delelighetsregler via tverrsum

Fordi \(10 \equiv 1 \pmod 3\) og \(10 \equiv 1 \pmod 9\), er ethvert tall kongruent med sin tverrsum modulo 3 og 9. Derfor: tallet er delelig på 3 (hhv. 9) nøyaktig når tverrsummen er det. For 11 gjelder \(10 \equiv -1 \pmod{11}\), så den alternerende sifferssummen avgjør delelighet på 11.

Eksempel 5: Er 5823 delelig på 9?

Tverrsum: \(5+8+2+3 = 18\)

\(9 \mid 18 \Rightarrow\) ja, \(5823 = 9\cdot 647\)

Studieguide: Tallteori og modulær aritmetikk

Studieguide: Tallteori og modulær aritmetikk