2
$\begingroup$

How to prove that $$ 7(100 ^{100}) + 8 \equiv 3^{90} - 21\ (\mathrm{mod} 28)?$$


I assumed the statement to be true. Then went on to show that both sides have the same remainder when divided by $28$.

$7(100)(100^{99}) + 8$ gives a remainder of $8$ when divided by $28$.

I don't know how to get the same remainder from $3^{90} - 21$.

$\endgroup$
  • $\begingroup$ You have that $3^3 \equiv 27 \equiv -1 \mod 28$. Use this to show that $3^{90} \equiv 1 \mod 28$. Are you sure that the LHS is equivalent with 8 mod 28? $\endgroup$ – Student Feb 24 '17 at 17:57
3
$\begingroup$

You know that $$3^3\equiv 97\equiv -1\pmod{28}.$$

So

$$3^{90}-21\equiv (-1)^{30}-21\equiv 8\pmod{28}.$$

And you can check that $$100^4\equiv 100\pmod {28}$$

so

$$7(100^{100})+8\equiv 7\times 100+8\equiv 8\pmod{28}.$$

So this statement is true.

$\endgroup$
  • $\begingroup$ You have made an error: $3^3 = 27$... $\endgroup$ – Student Feb 24 '17 at 17:59
  • $\begingroup$ @Student You are right :) I edited since. $\endgroup$ – E. Joseph Feb 24 '17 at 17:59
3
$\begingroup$

to calculate the remainder of $3^{90}-21$ you should use eulers theorem on the left side, notice $\varphi(28)=12$, so $3^{90}=3^{84}3^6\equiv 3^6\equiv 27^2\equiv 1 \bmod 28$, Hence $3^{90}-21\equiv 1-21\equiv-20\equiv 8\bmod 28$

$\endgroup$
0
$\begingroup$

As you have observed, $7\cdot 100^{100} \equiv 0 \bmod 28$. So what we want to prove then is $3^{90}\equiv 8+21\equiv29\equiv 1 \bmod 28$

The Carmichael function $\lambda(28)={\rm lcm}(\lambda(4),\lambda(7)) = {\rm lcm}(2, 6) = 6$ means that the cycle of values for $3^k \bmod 28$ is either $6$ in length or divides $6$ in length, and since $\gcd(3,28)=1$ then we know $3^6\equiv 1 \bmod 28$. In fact we can also see this directly since $3^3=27\equiv-1\bmod 28$ (but this discovery is not needed).

So since $3^6\equiv 1 \bmod 28$ then also $3^{90}\equiv (3^6)^{15}\equiv 1^{15}\equiv 1\bmod 28 $ and the result holds.

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