Fermat's little theorem and congruence equations

Fermat's little theorem and congruence equations Flashcards

Spec 5.4 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
State Fermat's little theorem.
If pp is prime and p∤ap\nmid a, then ap−1≡1(modp)a^{p-1}\equiv1\pmod p.
Alternative form of Fermat's little theorem?
ap≡a(modp)a^p\equiv a\pmod p for any integer aa.
How do you reduce ak(modp)a^k\pmod p?
Write k=q(p−1)+rk=q(p-1)+r; then ak≡ar(modp)a^k\equiv a^r\pmod p.
Least positive residue of 4204^{20} modulo 77?
420≡42=16≡24^{20}\equiv4^2=16\equiv2.
Remainder when 125012^{50} is divided by 77?
12≡512\equiv5, 550≡52=25≡45^{50}\equiv5^2=25\equiv4.
When does ax≡b(modn)ax\equiv b\pmod n have a solution?
If and only if hcf(a,n)\text{hcf}(a,n) divides bb.
How many solutions modulo nn does it have?
Exactly d=hcf(a,n)d=\text{hcf}(a,n) solutions (when d∣bd\mid b).
What is the multiplicative inverse of aa modulo nn?
A number xx with ax≡1(modn)ax\equiv1\pmod n; it exists iff hcf(a,n)=1\text{hcf}(a,n)=1.
How do you find a multiplicative inverse?
Euclidean algorithm, then Bezout back substitution: ax+ny=1ax+ny=1 gives ax≡1ax\equiv1.
Inverse of 1717 modulo 4040?
3333 (or −7-7), since 17×33=561≡1(mod40)17\times33=561\equiv1\pmod{40}.
Solve 7x≡3(mod11)7x\equiv3\pmod{11}.
Inverse of 7 is 8, so x≡24≡2(mod11)x\equiv24\equiv2\pmod{11}.
Solve a congruence when d=hcf(a,n)>1d=\text{hcf}(a,n)>1 and d∣bd\mid b.
Divide through by dd (including the modulus), solve, then list dd solutions modulo nn.

Flashcards