2
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.