# For $(a,b)=1$ and $n\in\mathbb{N}$ s.t. $a^{2^n} + b^{2^n} \equiv 0 \mod p$ prove that $2^{n+1} \mathrel{|} p - 1$

Let $$a$$ and $$b$$ be coprime integers and $$p$$ a prime number, such that for some $$n \in \mathbb{N}$$: $$a^{2^n} + b^{2^n} \equiv 0 \mod p$$ Prove that $$2^{n+1}\mid p - 1$$.

My attempt:

Consider the group $$G = (\mathbb{Z}/p\mathbb{Z})^\times$$, $$G$$ is cyclic and $$|G| = p-1$$.

$$a^{2^n} \equiv -b^{2^n} \mod p \iff a^{2^{n+1}} \equiv b^{2^{n+1}} \mod p$$. Since $$G$$ is cyclic it means $$G = \langle g\rangle$$ and $$a = g^k$$ and $$b = g^m$$ for some $$k$$ and $$m$$. Then $$(g^k)^{2^{n + 1}} \equiv (g^m)^{2^{n+1}} \mod p \iff (g^{k-m})^{2^{n+1}} \equiv 1 \mod p \implies p-1 = |g| \mid (k-m)2^{n+1}$$... I can't really go anywhere from here and I'm not even sure this is the correct way of approaching the problem. I'm thinking Lagrange's theorem can be used somewhere in the proof but I'd have to construct a subgroup of order $$2^{n+1}$$ which I'm not sure how to do. Some help would be greatly appreciated.

• Use \langle and \rangle, not < and >. Mar 30 at 18:45
• Also, \mid will produce an operator, and is generally better than \mathrel{|}. Mar 30 at 18:47

Steps, in outline:

1. Show $$b$$ cannot be divisible by $$p.$$
2. Solve $$bx\equiv 1\pmod p$$
3. Show $$(ax)^{2^n}\equiv -1\pmod p.$$
4. Show this means $$2^{n+1}$$ must be the multiplicative order of $$ax$$
5. Conclude $$2^{n+1}\mid p-1.$$

You don't really need $$(a,b)=1.$$ This is true if one if one merely assume $$p\not\mid b$$ or, equivalently $$p\not\mid a.$$

remark that both $$a^{2^{n}}$$ and $$b^{2^{n}}$$ are invertible in $$\mathbb{Z}/p\mathbb{Z}$$ (otherwise $$p$$ would be a common factor),so the first equality can be written as: $$(ab^{-1})^{2^{n}}=-1[p]$$ hence $$\vert ab^{-1} \vert ={2^{n+1}}$$ so $$2^{n+1} \vert p-1$$ (the order of an element divides that of the group).

• In general, in modular arithmetic, we tend t9 not to write $a/b,$ preferring $ab^{-1},$ just to make clear what we mean. Mar 30 at 15:48
• In general, for abelian multiplicative groups, we don't use division notation. That is slightly odd and inconsistent, because in additive abelian groups, we do use the minus sign. Mar 30 at 15:51
• @ThomasAndrews I will edit the post. Mar 30 at 15:59
• @belkacemabderrahmane How does $|ab^{-1}| = 2^{n+1}$ directly follow from $(ab^{-1})^{2^n} \equiv -1 \mod p$? Mar 30 at 16:22
• @Marin the order of $-1$ is $2$ and $(2^{n})^{2}=2^{n+1}$ Mar 30 at 19:35