Which of these congruences are correct?

Question

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

Dr. Sonnhard Graubner · Accepted Answer · 2017-10-09 08:59:44Z

0

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

answered Oct 9 '17 at 8:59

1

add a comment |

1 Answer 1