kongruens

Hej

jag har en uppgift där jag inte riktigt förstår hur man kommit fram till svaret.

Uppgiften är:

Om gcd(a,30)=1, visa att 60 delar $a^{4} + 59$

I svaret ser jag att dom börjat med att konstatera att om gcd(a,30)=1 så gäller det att gcd(a,5)=1 och därmed $a^{5 - 1} \equiv 1 (m o d 5)$ vilket kan skrivas som $a^{4} \equiv 1 (m o d 5)$ och därmed $a^{4} + 59 \equiv 0 (m o d 5)$

Sedan gör dom samma sak med $a^{3 - 1} \equiv 1 (m o d 3)$

men jag förstår inte hur man vet att man ska ta mod5 och mod3? och hur vet man att $a^{5 - 1} \equiv 1 (m o d 5)$

De använder sig av Fermats lilla sats säger att om p och a är relativ prim och p är prim så gäller $a^{p - 1} \equiv 1 (m o d p)$

EDIT: Det är ett specialfall av en av Eulers satser $a^{φ (n)} = 1 (m o d n)$ och $φ (n)$ är Eulers fi-funktion vilket är antalet tal mindre än n som är relativt prim till n

Primfaktorerna i 30 är intressanta, och de är ju 2, 3 och 5. Faktorn 2 måste man också säga något om.

Svara