2

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?

Evargalo
  • 2,593
Arnold Doveman
  • 1,095
  • 1
    Hint : Reduce the bases modulo $47$ , then $a)$ and $c)$ are easy to verify. – Peter Oct 09 '17 at 08:50
  • To verify $d)$ , reduce the exponent modulo $46$. The result is that only $b)$ is false. – Peter Oct 09 '17 at 08:54
  • I dont understand what is meant by 'reducing the bases module 47'. Could you perhaps give an example? – Arnold Doveman Oct 09 '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 09 '17 at 12:10
  • But how does that help in determining $1082^{551}$ modulo $47$? – Arnold Doveman Oct 09 '17 at 12:38
  • To solve $a)$ and $b)$, use $$1082^{551}\equiv 1^{551}=1\mod 47$$ $$1080^{551}\equiv (-1)^{155}=-1\mod 47$$ For $d)$, use $$1079^{553}\equiv 1079^1=1079\mod 47$$ because of $$553\equiv 1\mod 46$$ Note that the base can be reduced modulo $47$, and the exponent can be reduced modulo $\phi(47)=46$ , where $\phi(n)$ denotes the totient-function. – Peter Oct 09 '17 at 17:12

1 Answers1

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

Dr. Sonnhard Graubner
  • 95,283