Saturday, 18 October 2025

Exercise (1.2).6

Prove that for any integer $a$ we have $11 \mid (a^{11}− a)$.


We first recognise that $(a^{11}-a) = a(a^{10}-1)$.


Well consider two cases, $\gcd(a,11)=1$ and $\gcd(a,11) \ne 1$. 


Case $\gcd(a,11)=1$ for $(a^{10}-1)$

Well use the Division Algorithm: for integers $a$ and $b \ge 1$ there exist integers $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$.

Choosing $b=11$, then $0 \le r < 11$, and

$$\begin{gather*} a^{10}-1 =  11 q (2357947691 q^9 + 2143588810 q^8 r + \\ 876922695 q^7 r^2 + 212587320 q^6 r^3 + 33820710 q^5 r^4 + 3689532 q^4 r^5 + \\ 279510 q^3 r^6 + 14520 q^2 r^7 + 495 q r^8 + 10 r^9) + r^{10} - 1\end{gather*}$$

The first part is divisible by 11, so we focus on $r^10 -1$.

Since $\gcd(a,11)=1$ we have $r \ne 0$. This means $r$ can be 1,2,3,4,5,6,7,8,9,10,

$r=1$ means $r^10-1=0$, which is divisible by 11.

$r=2$ means $r^10-1=1023$, which is divisible by 1.

$r=3$ means $r^10-1=59048$, which is divisible by 11.

$r=4$ means $r^10 -1 = 1048575$, which is divisible by 11.

$r=5$ means $r^10-1 = 9765624$, which is divisible by 11.

$r=6$ means $r^10-1 = 60466175$, which is divisible by 11.

$r=7$ means $r^10-1 = 282475248$, which is divisible by 11.

$r=8$ means $r^10-1 = 1073741823$, which is divisible by 11.

$r=9$ means $r^10-1 = 3486784400$, which is divisible by 11.

$r=10$ means $r^10-1 = 9999999999$, which is divisible by 11.

So, for $\gcd(a,11)=1$ we have $11 \mid (a^{10}-1)$.


Case $\gcd(a,11)\ne 1$ for $a$

Because 11 only has two factors, 1 and 11, and 1 is excluded in this case, we're left with only $\gcd(a,11)=11$. This tells us $11\mid a$.


The two cases combined tell us that for any integer $a$ we have $11 \mid (a^{11}− a)$.