Show that for all odd integers: $a^{2^n} \equiv 1 \pmod {2^{n+2}}$

Question

Show that : $a^{2^n} \equiv 1 \pmod {2^{n+2}}$ for all odd integers.

The question states to show that all odd integers satisfy the 3 congruence:
1. $a^4 \equiv 1 \pmod{16}$
2. $a^8 \equiv 1 \pmod{32}$
3. $a^{16} \equiv 1 \pmod{64}$
and then to show that in general, the main question is satisfied.

It is obvious that induction is implied for the main question, with (weak) type needed.

I am attempting these 3 :
1. Let, $a=2k+1, \exists k \in \mathbb{Z}$.
For (1), $a^4 = (2k+1)^4 = 16k^4 + 32k^3 +24k^2 +8k+1$
Taking out $1$ to the l.h.s., we get:
$a^4 - 1= 8k(2k^3 + 4k^2 +3k +1)$
It is obvious that am unable to show common factor as 16.

I will attempt rest once am clear what is wrong in the first one.

Based on inputs, have got formula amended for factoring out $16$, as: $16k(k^3 + 2k^2 +k) + 16\cdot C(k+1,2)$,
as $16\cdot C(k+1,2) \implies 8(k+1)k \implies 8k^2 + 8k$

For, the second case:
2. $a^8 \equiv 1 \pmod{32}$
$(2k+1)^8 = 2^8k^8 + 8\cdot2^7k^7 +28\cdot2^6k^6 + 56\cdot2^5k^5 + 70\cdot 2^4k^4 + 56\cdot2^3k^3 + 28\cdot2^2k^2 + 8\cdot2k + 1$

=> $(2k+1)^8 - 1 = 2^5(2^3\cdot k^8 + 2^5\cdot k^7 +56\cdot k^6 + 56\cdot k^5 + 35\cdot k^4 + 14\cdot k^3) + 112k^2 + 16k$

Am stuck again, as do not know how to find a suitable formula that gels with the earlier case's. It should yield 3 terms, after taking in $16$ as common factor:
=> $16(x\cdot k^3 + 7\cdot k^2 + k)$,
where $x$ should resemble earlier case, and so $x=16$.
This leads to :
=> $(2k+1)^8 - 1 = 2^5(2^3\cdot k^8 + 2^5\cdot k^7 +56\cdot k^6 + 56\cdot k^5 + 35\cdot k^4 + 6\cdot k^3) + ( 256k^3 + 112k^2 + 16k)$
$(256k^3 + 112k^2 + 16k) = 16(16k^3 + 7k^2 + k)$
Am stuck again, as have no such formula in mind.

Based on a great answer by @Szeto, have got a different approach that considers the modified-residue (which is: residue $-1 \equiv 0\pmod {32}$) only, and then proves that $32$ must be a factor of residue.
The modified-residue is given by : $256k^3 + 112k^2 + 16k$, and in fact there is no need to take out $256k^3$ from its earlier grouping, as the job can be done by the : $112k^2 + 16k$ part only.

=> $16k(7k + 1)$, where it can be shown that $k(7k+1)$ is always divisible by 2 for any integer (odd, or even) $k$.

Hence, proved for case 2.

For, the third case:
3. $a^{16} \equiv 1 \pmod{64}$
will ignore terms with the powers of $2k \ge 5$, and see how more trimming of expressions can be done:

Answer by @Szebo has shown how to use the result of case (2) for case (3).

You think you run into problems if $k$ is odd. So try $k=1$ and verify that $a=3$, $a^4=81\equiv 1\pmod{16}$. Where does your derivation fail for this case? — Hagen von Eitzen, Jan 17 '18 at 08:30
And this can be proved by induction on $n$ for $n \geqslant 1$. — Ѕᴀᴀᴅ, Jan 17 '18 at 08:32
Btw, why do you even test the cases $n=2,3,4$, when ultimately you will do induction starting from $n=1$? — Hagen von Eitzen, Jan 17 '18 at 08:33
@Hagen von Eitzen Not think that an example should help, when formula is so straight for modulo arithmetic. As per me, induction's need is a grey area here. — jiten, Jan 17 '18 at 08:34
$\displaystyle8k(2k^3 + 4k^2 +3k +1)=16k(k^3 + 2k^2 +k)+8k(k+1)=16k(k^3 + 2k^2 +k)+16\binom{k+1}2$ — , Jan 17 '18 at 08:35
@ProfessorVector Thanks for that, if don't mind please tell how to express the combinations by your syntax. — jiten, Jan 17 '18 at 08:43
@ProfessorVector Please help as am stuck again, for the second case. Unable to find an expression with common term $16$. — jiten, Jan 17 '18 at 09:51
@ProfessorVector Please help, as all errors have been removed. — jiten, Jan 17 '18 at 10:16

Szeto · Accepted Answer · 2018-01-17T10:58:37.773

1

Here I will do(part of) the proof of the general statement by M.I.:

Suppose when $n=k$(odd) the following is true for all odd $a$: $$a^{2^k} \equiv 1\pmod{2^{k+2}}$$

Then, for some integer $c$, $$a^{2^k} = c*2^{k+2} + 1$$.

When $n=k+2$, LHS = $$a^{2^{k+2}} = a^{2^k*4} = {a^{2^k}}^4 = (c*2^{k+2} + 1)^4$$.

And this can be expanded to: $$=c^4 2^{4k+8} + 4c^3 2^{3k+6} + 6c^2 2^{2k+4} + 4c 2^{k+2} +1$$

All terms except the last one are divisible by $2^{k+4}$. Note that the second last term is indeed divisible by $2^{k+4}$ since $4c 2^{k+2} = c 2^{k+4}$.

Thus the remainder is $1$ as expected.

You still need to prove that when $n=1$ the general statement is true for all odd $a$. That could be done easily by M.I.. ———————————-

In case (2), as the OP has derived, $$(2k+1)^8 \equiv 256k^3+112k^2+16k+1\pmod{32}$$.

Obviously, $256k^3$ is divisible by 32. So (the part of interest of) the original expression is reduced to: $$112k^2+16k=2^4(k)(7k+1)$$.

Obviously, as long as $k(7k+1)$ is even, the above expression is divisible by $32=2^5$.

When $k$ is odd, $7k+1$ is even, and the product of them is even as well. When $k$ is even, $k(7k+1)$ is even as well. Therefore, $k(7k+1)$ is always even.

As a result $2^4(k)(7k+1)$ is always divisible by 32.

Thus, $$(2k+1)^8 \equiv 1\pmod{32}$$

For case (3), there is a shortcut that avoids binomial expansion.

As we have proven the above result, we can write down for integer $b$: $$a^8=32b+1$$.

Therefore, $$a^{16}=(a^8)^2=(32b+1)^2=32^2b^2+64b+1\equiv 1\pmod{64}$$ as expected.

This indeed implies that case (2) can be proven similarly by using the result of case (1).

edited Jan 17 '18 at 10:58

answered Jan 17 '18 at 09:21

Szeto

11,159

Please see my second case, in edited OP. I am stuck there. – jiten Jan 17 '18 at 09:53
1

@jiten I have edited my answer. – Szeto Jan 17 '18 at 10:21
What a bliss, so much thankful. – jiten Jan 17 '18 at 10:24
@jiten Please give it a green tick if you do appreciate it! – Szeto Jan 17 '18 at 10:25
I wish I could do more ticks. – jiten Jan 17 '18 at 10:27
Please advise any shorter route for case 3, as while doing it am feeling it is too cumbersome, as power is $16$ now. If, some way to shorten the proof itself, that does not need binomial expansion, then would be a lot better. – jiten Jan 17 '18 at 10:47
1

@jiten Please see my edited answer. – Szeto Jan 17 '18 at 10:59
Thanks again for the new approach. – jiten Jan 17 '18 at 11:38

Show that for all odd integers: $a^{2^n} \equiv 1 \pmod {2^{n+2}}$

1 Answers1