1

I was trying to prove this equation I did these but I don't know what to do next?!

$2^a-1\equiv 2^{a\ \bmod\ b}-1 \ \bmod\ (2^b -1)$

My solution:

$$ a = cb+r$$ $$ 2^{cb+r} \equiv 2^r (\bmod \ 2^b -1) $$ $$ 2^{cb} \equiv 1 (\bmod \ 2^b -1) $$ (in this line I should prove that $gcd(2^b-1,2^r)=1$

and I dont know what to do next! any suggestions?

Cookie
  • 13,532
ReZa
  • 189
  • Just fot clarity, isn't the RHS $(2^{a \text{mod} b}-1)\text{mod} (2^b - 1)$? – tpb261 May 29 '14 at 03:06
  • for $a=12$ and $b=9$, I get $1023 \equiv 8 - 1 (mod 511)$. I'm fairly sure this isn't valid. – tpb261 May 29 '14 at 03:14
  • it is $2^a - 1$ not $2^{a-1}$ I know you can remove -1 from both side, but the question was this form!! – ReZa May 29 '14 at 10:53
  • Can you check my second comment? – tpb261 May 29 '14 at 11:27
  • Yes that's Ok $2^{12} -1 = 4095$ so $4095 \equiv 7\ (mod511)$ is ok! – ReZa May 29 '14 at 11:29
  • you want to prove: $gcd(2^b−1,2^r)=1$? There's nothing to prove there, $2^b-1$ is an odd number and $2^r$ is an even number with no odd factors, so, their is gcd is 1. But I think, I didn't get how you would go ahead with that. – tpb261 May 29 '14 at 11:52
  • A part was proving what you said And then "and I dont know what to do next! " ! – ReZa May 29 '14 at 12:02

1 Answers1

0

From: $ 2^{cb} \equiv 1 (mod \ 2^b -1) $

${\left(2^b\right)}^c \equiv 1 (mod \ 2^b -1)$

$1^c \equiv 1 (mod \ 2^b -1)$

$1 \equiv 1 (mod \ 2^b -1)$

Mick A
  • 10,208