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

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!

-

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$.

-
The question actually appears in the notes a couple chapters prior to coverage of Fermat's little theorem. But, I think I'll be happy to just use it, if I can get somewhere with it. –  Jeff Aug 18 '12 at 12:05
However, it's not necessarily true that a is relatively prime to p. a is just a positive integer.. it could be a multiple of p? In which case, the little Fermat theorem wouldn't apply? –  Jeff Aug 18 '12 at 12:08
If $a$ is not relatively prime to $p$, then $a\equiv0\pmod p$, and no power of $a$ will be $\pm1$ modulo $p$. –  Gerry Myerson Aug 18 '12 at 12:17
I just realised this and came back to say I was mistaken. Thanks! –  Jeff Aug 18 '12 at 12:28

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.

-
For full credit, come back to this after you have covered basics of group theory! –  Jyrki Lahtonen Aug 18 '12 at 12:37
I reallly appreciate how much time you must have spent writing this up. I've sat here trying to understand it for about 30mins.. but I just can't get my head around certain parts. I'm just a bit too dumb. It would have been fascinating to sit through this with you though, because clearly you've got the ability to break things up into nice parts with relevant questions. –  Jeff Aug 18 '12 at 12:47
@Jeff: My first question is kinda difficult. To get an idea of what the sets $[m]$ look like you could compute by hand a few of them in the cases: A) $x=17$, $a=2$ (when $a^4\equiv-1$) and B) $x=41$, $a=3$ (when, again $a^4\equiv -1$). –  Jyrki Lahtonen Aug 18 '12 at 13:02