2
$\begingroup$

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!

2 Answers 2

2

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

  • 0
    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.2012-08-18
  • 0
    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?2012-08-18
  • 0
    If $a$ is not relatively prime to $p$, then $a\equiv0\pmod p$, and no power of $a$ will be $\pm1$ modulo $p$.2012-08-18
  • 0
    I just realised this and came back to say I was mistaken. Thanks!2012-08-18
0

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 mHow 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

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.

  • 0
    For full credit, come back to this after you have covered basics of group theory!2012-08-18
  • 0
    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.2012-08-18
  • 0
    @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$).2012-08-18