Fermat's little theorem and congruence equationsEdexcel A-Level Further Maths: Revision notes

Fermat's little theorem: if $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv1\pmod p.$ An equivalent form is $a^p\equiv a\pmod p$ for every integer $a$. The proof is not required. Example: $p=7$, $a=4$: $4^6\equiv1\pmod7$. Check: $4^3=64=63+1\equiv1$, so $4^6\equiv1$ as well.

To find $a^k\pmod p$: write $k=q(p-1)+r$ with $0\leq r<p-1$. Then $a^k=(a^{p-1})^q\,a^r\equiv a^r\pmod p$. Example: $4^{20}\pmod7$. $20=3\times6+2$, so $4^{20}\equiv4^2=16\equiv2$. Example: $12^{50}\pmod7$: $12\equiv5$ and $50=8\times6+2$, so $12^{50}\equiv5^2=25\equiv4$. Reduce the base first, then the exponent.

Let $d=\text{hcf}(a,n)$. The congruence $ax\equiv b\pmod n$ has a solution if and only if $d\mid b$. When it does, there are exactly $d$ solutions modulo $n$, and if $d=1$ there is a unique solution modulo $n$. Examples: $6x\equiv4\pmod9$ has no solution ($d=3\nmid4$). $6x\equiv9\pmod{15}$: $d=3\mid9$, so $3$ solutions modulo $15$ ($4,9,14$).

If $\text{hcf}(a,n)=1$, Bezout gives $ax+ny=1$, so $ax\equiv1\pmod n$: $x$ is the multiplicative inverse of $a$ modulo $n$. Find it with the Euclidean algorithm and back substitution. Example: $40=2(17)+6$, $17=2(6)+5$, $6=1(5)+1$, so $1=3(40)-7(17)$ and the inverse of $17$ modulo $40$ is $-7\equiv33$. Check: $17\times33=561=14(40)+1$. To solve $ax\equiv b$, multiply by the inverse: $17x\equiv9$ gives $x\equiv9\times33=297\equiv17\pmod{40}$.

If $d=\text{hcf}(a,n)$ divides $b$, divide $a$, $b$ and $n$ by $d$ to get $a'x\equiv b'\pmod{n'}$, which has $\text{hcf}(a',n')=1$ and a unique solution $x\equiv x_0\pmod{n'}$. The solutions modulo $n$ are $x_0,\;x_0+n',\;x_0+2n',\dots,x_0+(d-1)n'$. Example: $15x\equiv9\pmod{21}$. $d=3$, so $5x\equiv3\pmod7$. The inverse of $5$ is $3$, so $x\equiv9\equiv2\pmod7$. The solutions are $x=2,9,16$ modulo $21$.