2

I am having some trouble in proving that the only solutions to $$ -2^{m-1} \equiv m \pmod{7} $$

are $m \equiv 3,5, 13 \pmod{42}$.

What I tried to use:

If $-2^{m-1} \equiv m \pmod{7}$, then $2^{m-1} \equiv 6m \pmod{7}$ and we know that $2^6 \equiv 1 \pmod{7}$.

But now I can't go on. Could someone give me a hint of what should I be doing next?

JPLF
  • 590
  • 1
    You know better, namely $2^3\equiv1\mod7$, maybe that allows a congruence modulo $21$? – Lubin Sep 19 '12 at 18:14
  • 3
    The statement is wrong. It should be mod $21$, not mod $42$. – Robert Israel Sep 19 '12 at 18:20
  • If you have a copy of Stewart's Algebraic Number Theory, you can see that he states that these are the solutions, at page 98. (it's the 3rd edition) – JPLF Sep 19 '12 at 18:28

1 Answers1

2

Note that modulo $7$, $2^m$ is periodic with period $3$. So $2^{m-1}+m$, modulo $7$, is periodic with period at most $21$.

Now one only needs to make a somewhat long table, starting at $m=1$. The powers of $2$, modulo $7$, are $1,2,4,1,2,4,1,2,\dots$. And $m$ is congruent to $1,2,3,4,5,6,0,1,\dots$. Add, check where we get $0$ modulo $7$.

Note that it first happens when $m=3$, since $4+3\equiv 0\pmod{7}$. Thus it happens at any $m\equiv 3\pmod{21}$. It also happens at $m=5$, since $2+5\equiv 0\pmod{7}$. Continue.

Remark: Modulo $42$, there will be more solutions, since the period is $21$.

André Nicolas
  • 507,029