Find all $\displaystyle n,k\in\mathbb{N}$ for which $\displaystyle 53|2^k-2^n$.

Results 1 to 3 of 3

- Apr 3rd 2011, 05:49 AM #1

- Joined
- Nov 2007
- Posts
- 329

- Apr 3rd 2011, 07:37 AM #2

- Joined
- Oct 2009
- Posts
- 4,261
- Thanks
- 3

Choose $\displaystyle k>n\Longrightarrow k=n+m\,,\,m>0\Longrightarrow 53\mid (2^{n+m}-2^n)= 2^n(2^m-1)\iff$

$\displaystyle \iff 53\mid (2^m-1)\iff 2^m=1\!\!\pmod{53}$ , and since 2 is not a primitive

root modulo 53 (look here Primitive root modulo n - Wikipedia, the free encyclopedia) ,

the above is true only when...

Tonio

: Either the above link is wrong or else I didn't understand it. Anyway, 2 indeed is__Edit__

a primitive root modulo 53, and thus $\displaystyle 2^m=1\iff m=k-n=0\!\!\pmod {52}$

- Apr 3rd 2011, 12:57 PM #3

- Joined
- Jun 2010
- From
- Israel
- Posts
- 148

We have $\displaystyle k\geq n$. Write $\displaystyle 2^k-2^n=2^n(2^{k-n}-1)$. Since $\displaystyle (53,2^n)=1$, $\displaystyle 53 $ must divide $\displaystyle 2^{k-n}-1$, i.e $\displaystyle 2^{k-n}\equiv1\pmod{53}$.

Actually $\displaystyle 2 $ is a primitive root of $\displaystyle 53 $; hence the congruence holds if and only if $\displaystyle k-n\equiv0\pmod{52}$.

Now I think this is the answer:

For any fixed integer $\displaystyle t\geq0 $, the solutions are given by any pair $\displaystyle k, n $ such that $\displaystyle k-n=52t$.