Suppose $a^{2^{b}} \equiv −1 \pmod{x}$. show $x \equiv 1 \pmod{2^{b+1}}$.

Question

Let $x$ be an odd prime, and let $a$ and $b$ be positive integers, with $a \gt 1$.

Suppose $a^{2^{b}} \equiv −1 \pmod{x}$. Then $x \equiv 1 \pmod{2^{b+1}}$.

I have to solve using number theory concepts - it's homework for number theory.

---

I start by noting that: $$a^{2^{b+1}} ≡ 1 \pmod{x}$$

But I don't know where to go next.. I don't think I'm allowed to use concepts like the order of an element in a group (since we haven't even talked about groups in the class yet). Would greatly appreciate some direction, hints, anything!

Answer 1

Do you have the little Fermat theorem, the one that says that if $p$ is prime and $a$ is relatively prime to $p$ then $a^{p-1}\equiv1\pmod p$? From that, it's not hard to prove that if $a^r\equiv1\pmod p$ then $r$ divides $p-1$. Then if $a^r\equiv1\pmod x$ then $r$ divides $p-1$ for every prime $p$ dividing $x$. That is, $p\equiv1\pmod r$ for every $p$ dividing $x$. So $x$ is a product of primes, each of which is 1 modulo $r$. So $x\equiv1\pmod r$.

Answer 2

Hmm. The following argument (given using extended hints) disguises the basic bits about group theory (that you forbade). I don't know how many of these bits you have covered, so there is probably some overkill.

Let $m$ be any integer in the range $1\le m<x$. Consider the set of integers (or rather cosets modulo $x$) of the form $$ [m]=\{a'\mid 0<a' <x,\ ma^j\equiv a'\pmod x\ \text{for some natural number }j\}. $$ The first question I want to ask is: How many elements are there in the set $[m]$? Well, we places no restrictions on $j$, so we need to answer, when might we have the congruence $$ ma^j\equiv ma^{j'}\pmod x, $$ where $0\le j<j'$. We need $x$ to divide $m(a^{j'}-a^j)=ma^j(a^{j'-j}-1)$. Because $x$ is a prime, and $m,a$ are both between zero and $x$ this can only happen, if $a^{j'-j}\equiv 1\pmod x$. From the given bits it follows that $k=2^{b+1}$ is the smallest positive integer $k$ with the property that $a^k\equiv 1\pmod x$. Prove this! You need to observe that no smaller power of two will do. You also need to observe that if this holds for $k_1$ and $k_2$, then by Bezout's identity it will hold for $k=\gcd(k_1,k_2)$. You should now be well placed to conclude that $|[m]|=2^{b+1}$.

The next thing I want you to think about is: Is it possible that $[m_1]\cap[m_2]\neq\emptyset$? If $m_2a^{j_2}\equiv m_1a^{j_1}\pmod x$, then you can start cancelling the factors $a$. You should reach the conclusion that the intersection is non-empty, if and only if $m_2\in[m_1]$ and $m_1\in[m_2]$ in which case the two set coincide, i.e. $[m_1]=[m_2]$.

Now we are nearly done. Start with the set $\{1,2,\ldots,x-1\}$. Start casting out sets of the form $[m]$ for some $m$ still remaining. Conclude at each point that you are casting out exactly $2^{b+1}$ elements of this set (none of the newly casted were thrown out earlier). Eventually the set becomes empty, so conclude that the number of elements in the set must have been divisible by $2^{b+1}$ to begin with.