małe twierdzenie fermata i podzielność

[bzyk12]

Wykaż korzystajac z małego twierdzenia fermata, że jeżeli NWD(a,b)=1, to każdy dzielnik pierwszy p różny od 3 liczby \(\displaystyle{ a ^{2}+ab+b ^{2}}\) jest postaci p=6m+1

[Justka]

p=2 odpada. Niech p>3, wtedy \(\displaystyle{ p=6m+1 \ \vee \ p=6m+5}\). Załóżmy nie wprost, że każdy dzielnik pierwszy liczby \(\displaystyle{ a^2+ab+b^2}\) ma postać \(\displaystyle{ p=6m+5}\).

Z treści mamy \(\displaystyle{ p|a^2+ab+b^2 \ \Rightarrow p|(a-b)(a^2+ab+b^2)=a^3-b^3}\), czyli \(\displaystyle{ (\star) \ \ a^3 \equiv b^3 \ (\mod p)}\). Zaś skoro \(\displaystyle{ (a,b)=1}\) to \(\displaystyle{ (\star \star) \ \ a \neq b, \ (a,p)=1 \wedge (b,p)=1}\), zatem z MTF

\(\displaystyle{ a^{p-1} \equiv 1 \equiv b^{p-1} \ (\mod p)}\)

podstawiając \(\displaystyle{ p=6m+5}\) otrzymujemy

\(\displaystyle{ a^{6m+4} \equiv b^{6m+4} \ (\mod p)}\), a to w połączeniu z \(\displaystyle{ (\star)}\) daje nam \(\displaystyle{ a \equiv b \ (\mod p)}\)

ale wtedy \(\displaystyle{ a^2+ab+b^2 \equiv 3a^2 \equiv 0 \ (\mod p) \Rightarrow a \equiv 0 \ (\mod p)}\), sprzeczność z \(\displaystyle{ (\star \star)}\) dowodzi tezy zadania.