Results 1 to 3 of 3

Thread: 53|2^k-2^n

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    53|2^k-2^n

    Find all $\displaystyle n,k\in\mathbb{N}$ for which $\displaystyle 53|2^k-2^n$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by james_bond View Post
    Find all $\displaystyle n,k\in\mathbb{N}$ for which $\displaystyle 53|2^k-2^n$.


    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

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

    a primitive root modulo 53, and thus $\displaystyle 2^m=1\iff m=k-n=0\!\!\pmod {52}$
    Last edited by tonio; Apr 3rd 2011 at 02:11 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by james_bond View Post
    Find all $\displaystyle n,k\in\mathbb{N}$ for which $\displaystyle 53|2^k-2^n$.
    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$.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum