2
$\begingroup$

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?

  • 0
    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)2012-09-19

1 Answers 1

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

  • 0
    @Lubin: Thanks for the correction.2012-09-19