# Which of these congruences are correct?

a) $1082^{551} \equiv 1(\bmod 47)$

b) $1081^{552} \equiv 1(\bmod 47)$

c) $1080^{551} \equiv -1(\bmod 47)$

d) $1079^{553} \equiv 1079(\bmod 47)$

You have to use Fermat's little theorem which states that ....

if $p$ is a prime number and $a$ is a whole number such that $p \nmid a$, then

$$a^{p-1} \equiv 1(\bmod p)$$

From that I can immediately conclude that congruence $b)$ is not valid since $1081/47 = 23$

As for congruence $a)$ I use the fact that $551 = 46*11 + 45$ and from Fermat's little theorem get that

$$1082^{45} \equiv 1(\bmod 47)$$

But this is also too large of a number to evaluate, is there quick and clever way to check all these congruences?

• Hint : Reduce the bases modulo $47$ , then $a)$ and $c)$ are easy to verify. – Peter Oct 9 '17 at 8:50
• To verify $d)$ , reduce the exponent modulo $46$. The result is that only $b)$ is false. – Peter Oct 9 '17 at 8:54
• I dont understand what is meant by 'reducing the bases module 47'. Could you perhaps give an example? – Arnold Doveman Oct 9 '17 at 12:05
• $1082=23\cdot 47+1$ , so $1082$ modulo $47$ is $1$, so you can replace $1082$ by $1$. And $1080=23\cdot 47-1$, so you can replace $1080$ by $-1$ – Peter Oct 9 '17 at 12:10
• But how does that help in determining $1082^{551}$ modulo $47$? – Arnold Doveman Oct 9 '17 at 12:38

for a) this is right for b),c) we have $1081=23\cdot 47$ so the given result is wrong, i must be $0$ d) $$1079^{553}=1079\equiv 45\mod 47$$