Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
1  
Sorry, I think that $2^m$ is periodic with period $3$. –  Lubin Sep 19 '12 at 18:15
    
@Lubin: Thanks for the correction. –  André Nicolas Sep 19 '12 at 18:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.