Which of these congruences are correct?

268 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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$$