MHB Show that a^(2n)≡1 (mod 2^(n+2))

[evinda]

Hi! (Smile)

I am looking at the following exercise:

$$\text{Let an odd } a. \text{ Prove that : } \\ \ \ \ \ a^{2^n} \equiv 1 \pmod {2^{n+2}} $$

I thought that we could use the Euler's theorem but I found:

$$m=2^{n+2} , (a,m)=1 \text{ since } a \text{ is an odd number,so } 2 \nmid a$$

$$\phi(m)=2^{n+2}-2^{n+1}=2^{n+1}$$

So,we get $a^{2n+1} \equiv 1 \pmod {2^{n+1}}$.

But,we want to show that $a^{2n} \equiv 1 \pmod {2^{n+2}}$.How can we do this? (Thinking) (Thinking)

 

[Nono713]

The claim is not true. Take $n = 5$ and $a = 3$, then:

$$a^{2n} \equiv 3^{10} \equiv 59049 \equiv 41 \pmod{2^7}$$

You really should verify claims with a few numbers before trying to prove them... I suspect you might have meant $a^{2^n}$.

 

[evinda]

The claim is not true. Take $n = 5$ and $a = 3$, then:

$$a^{2n} \equiv 3^{10} \equiv 59049 \equiv 41 \pmod{2^7}$$

You really should verify claims with a few numbers before trying to prove them... I suspect you might have meant $a^{2^n}$.

Yes,I meant $a^{2^n}$.. (Nod)

 

[Nono713]

Maybe the binomial theorem could help. First assume $a^{2^n} \equiv 1 \pmod{2^{n + 2}}$ for some odd $a$. Like, for instance, $a = 1$. Then pose:
$$(a + 2)^{2^n} \equiv \sum_{k = 0}^{2^n} \binom{2^n}{k} a^{2^n - k} 2^k \pmod{2^{n + 2}}$$
Show that almost all terms of the sum are multiples of $2^{n + 2}$ (by putting lower bounds on the binomial coefficient and counting factors of two) and find that the remaining terms for $k > 0$ happen to cancel out, leaving the $k = 0$ term which is of course $1$. Conclude by induction.

I haven't tried it. I think it might be worth a shot, doubtful though. Most likely this calls for a true number-theoretic argument, or perhaps a group-theoretic proof (since the claim amounts to saying that every element of $(\mathbb{Z}/2^{n + 2} \mathbb{Z})^\times$ has order at most $2^n$, whereas the group has order $2^{n + 1}$).

 

[I like Serena]

Hi! ;)

$$\phi(m)=2^{n+2}-2^{n+1}=2^{n+1}$$

So,we get $a^{2n+1} \equiv 1 \pmod {2^{n+1}}$.

I think you mean $a^{2^{n+1}} \equiv 1 \pmod {2^{n+2}}$.

It almost looks like a Legendre symbol or a Jacobi symbol, except that $2^{n+2}$ is not an odd prime, nor an odd composite.
But $a^{2^n}$ would be either $1$ or $-1 \pmod{2^{n+2}}$.

Anyway, I don't see a way to find it yet. (Doh)

 

[evinda]

Maybe the binomial theorem could help. First assume $a^{2^n} \equiv 1 \pmod{2^{n + 2}}$ for some odd $a$. Like, for instance, $a = 1$. Then pose:
$$(a + 2)^{2^n} \equiv \sum_{k = 0}^{2^n} \binom{2^n}{k} a^{2^n - k} 2^k \pmod{2^{n + 2}}$$
Show that almost all terms of the sum are multiples of $2^{n + 2}$ (by putting lower bounds on the binomial coefficient and counting factors of two) and find that the remaining terms for $k > 0$ happen to cancel out, leaving the $k = 0$ term which is of course $1$. Conclude by induction.

I haven't tried it. I think it might be worth a shot, doubtful though. Most likely this calls for a true number-theoretic argument, or perhaps a group-theoretic proof (since the claim amounts to saying that every element of $(\mathbb{Z}/2^{n + 2} \mathbb{Z})^\times$ has order at most $2^n$, whereas the group has order $2^{n + 1}$).

Hi! ;)
I think you mean $a^{2^{n+1}} \equiv 1 \pmod {2^{n+2}}$.

It almost looks like a Legendre symbol or a Jacobi symbol, except that $2^{n+2}$ is not an odd prime, nor an odd composite.
But $a^{2^n}$ would be either $1$ or $-1 \pmod{2^{n+2}}$.

Anyway, I don't see a way to find it yet. (Doh)

I have an idea! (Wait)

$$a^{2^n}-1=a^{2 \cdot 2^{n-1}}-1=(a^{2^{n-1}})^2-1=(a^{2^{n-1}}-1)(a^{2^{n-1}}+1)=(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)=(a^{2^{n-3}}-1)(a^{2^{n-3}}+1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)= \dots= \\ =(a^{2^{n-1}}+1)(a^{2^{n-2}}+1)(a^{2^{n-3}}+1) \cdots (a^2+1)(a-1)(a+1) \overset{a \text{ is odd } \Rightarrow \text{ power of a is also odd } }{ = } \\ 2k_1 \cdot 2k_2 \cdot 2k_3 \cdots 2k_{n-1}(a-1)(a+1) (*)$$

$$a=2k+1$$
$$a+1=2k+2$$
$$a-1=2k$$

$$(a+1)(a-1)=4k(k+1)$$
$$k,k+1 \text{ are consecutive,so one of them is even.Therefore,the product } 4k(k+1)=8k'$$

$$(*)=2^{n-1} \cdot 2^3 \cdot k_1 \cdot k_2 \cdots k_{n-1} \cdot k'=2^{n+2} \cdot m$$

So,we conclude that $\displaystyle{2^{n+2} \mid a^{2^n}-1}$.

Therefore,

$$a^{2^n} \equiv 1 \pmod{2^{n+2}}$$

(Happy)

 

[I like Serena]

I have an idea! (Wait)

$$a^{2^n}-1=a^{2 \cdot 2^{n-1}}-1=(a^{2^{n-1}})^2-1=(a^{2^{n-1}}-1)(a^{2^{n-1}}+1)=(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)=(a^{2^{n-3}}-1)(a^{2^{n-3}}+1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)= \dots= \\ =(a^{2^{n-1}}+1)(a^{2^{n-2}}+1)(a^{2^{n-3}}+1) \cdots (a^2+1)(a-1)(a+1) \overset{a \text{ is odd } \Rightarrow \text{ power of a is also odd } }{ = } \\ 2k_1 \cdot 2k_2 \cdot 2k_3 \cdots 2k_{n-1}(a-1)(a+1) (*)$$

$$a=2k+1$$
$$a+1=2k+2$$
$$a-1=2k$$

$$(a+1)(a-1)=4k(k+1)$$
$$k,k+1 \text{ are consecutive,so one of them is even.Therefore,the product } 4k(k+1)=8k'$$

$$(*)=2^{n-1} \cdot 2^3 \cdot k_1 \cdot k_2 \cdots k_{n-1} \cdot k'=2^{n+2} \cdot m$$

So,we conclude that $\displaystyle{2^{n+2} \mid a^{2^n}-1}$.

Therefore,

$$a^{2^n} \equiv 1 \pmod{2^{n+2}}$$

(Happy)

Nice! (Cool)

 

[Opalg]

Alternatively, I think you could probably prove it by induction, as in http://mathhelpboards.com/challenge-questions-puzzles-28/remainder-10872.html#post50306.

 

[evinda]

Alternatively, I think you could probably prove it by induction, as in http://mathhelpboards.com/challenge-questions-puzzles-28/remainder-10872.html#post50306.

A ok...Thanks a lot! (Mmm)

 

[sang747]

I have an idea! (Wait)

$$a^{2^n}-1=a^{2 \cdot 2^{n-1}}-1=(a^{2^{n-1}})^2-1=(a^{2^{n-1}}-1)(a^{2^{n-1}}+1)=(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)=(a^{2^{n-3}}-1)(a^{2^{n-3}}+1)(a^{2^{n-2}}+1)(a^{2^{n-1}}+1)= \dots= \\ =(a^{2^{n-1}}+1)(a^{2^{n-2}}+1)(a^{2^{n-3}}+1) \cdots (a^2+1)(a-1)(a+1) \overset{a \text{ is odd } \Rightarrow \text{ power of a is also odd } }{ = } \\ 2k_1 \cdot 2k_2 \cdot 2k_3 \cdots 2k_{n-1}(a-1)(a+1) (*)$$

$$a=2k+1$$
$$a+1=2k+2$$
$$a-1=2k$$

$$(a+1)(a-1)=4k(k+1)$$
$$k,k+1 \text{ are consecutive,so one of them is even.Therefore,the product } 4k(k+1)=8k'$$

$$(*)=2^{n-1} \cdot 2^3 \cdot k_1 \cdot k_2 \cdots k_{n-1} \cdot k'=2^{n+2} \cdot m$$

So,we conclude that $\displaystyle{2^{n+2} \mid a^{2^n}-1}$.

Therefore,

$$a^{2^n} \equiv 1 \pmod{2^{n+2}}$$

(Happy)

Thank you for this nice idea. It illuminated me. :)