3
$\begingroup$

I have this one question which after some hours of thinking I can't seem to be getting anywhere. The question reads:

Show that $3^{22}-2^{20}$ is divisible by $7$.

Now, after using a calculator I know that this is true, but I can't seem to be able to see a good way to approach the problem.

I have tried factoring the expression, but it always led me to a dead end. I was wondering if anyone knows how to tackle the issue. Any hints or suggestions would be much appreciated!

$\endgroup$
  • 4
    $\begingroup$ Do you know Fermat's little theorem ? $\endgroup$ – Peter Sep 2 at 10:12
3
$\begingroup$

As $3^2\equiv2\pmod7$

$$3^{22}-2^{20}=(3^2)^{11}-2^{20}\equiv2^{11}-2^{20}\equiv-2^{11}(2^9-1)$$

Now $2^3\equiv1\pmod7\implies2^9=(2^3)^3\equiv1^3\pmod7$

Generalization:

$$3^{2n}-2^m\equiv2^n-2^m\pmod7$$

Now if $n\ge m, 2^n-2^m=2^m(2^{n-m}-1)$

As $2^3\equiv1\pmod7,$ we need $n-m$ to be divisible by $3$ for $2^n\equiv2^m\pmod7$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Of course. I feel like a such a dunce. Thank you very much! $\endgroup$ – Rebronja Sep 2 at 10:37
  • $\begingroup$ @Rebronja, Updated a bit $\endgroup$ – lab bhattacharjee Sep 2 at 12:38
3
$\begingroup$

Modulo $7$, you have $$3^{22}-2^{20} = (3^3)^7 \times 3 - (2^3)^6 \times 4= (-1)^7 \times 3 - 1^6 \times 4 = -3-4 = 0$$

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

$$3^{22} - 2^{20} = (3^{11} - 2^{10})(3^{11}+2^{10})$$

$$3^{11}+2^{10} \equiv 3^5 + 2^4 \equiv2+ 4 \cdot 3 \equiv 0 \mod 7$$

| cite | improve this answer | |
$\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.