Results 1 to 3 of 3

Math Help - Simple congruence

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    16

    Simple congruence

    Does \frac{2^x-1}{3}=n, n natural, have odd solutions in the naturals for x? How do you know (does Euler's theorem tell me this)?
    Last edited by sleepingcat; June 7th 2008 at 04:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by sleepingcat View Post
    Does \frac{2^n-1}{3} have odd solutions in the naturals? How do you know?
    All odd natural numbers (n) can be written n=2k+1, k \in \mathbb{N} \cup 0

    For the above to have solutions in the odd naturals this must be true for some k

     (2^{n}-1 \equiv 0 \mod \\\ {3}) \iff (2^{2k+1}-1 \equiv 0 \mod \\\ {3}) \iff (2\cdot 4^{k}-1 \equiv 0 \mod \\\ {3})

    but [4^k]=[4]^k=[1]^k mod 3

    (2\cdot 4^{k}-1 \equiv 0 \mod \\\ {3})\implies (2\cdot 1^{k}-1 \equiv 0 \mod \\\ {3}) \implies (2-1 \equiv 0 \mod \\\ {3})

    This false so there is not a solution.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by sleepingcat View Post
    Does \frac{2^x-1}{3}=n, n natural, have odd solutions in the naturals for x? How do you know (does Euler's theorem tell me this)?
    Note that 2^x - 1 = 1+2+2^2+...+2^{x-1} (this identity appears in The Elements).

    Next, 2 \equiv -1 (\bmod 3).
    Thus, 1+2+2^2+...+2^{x-1} = \pm 1(\bmod 3) (depending whether x is even or odd).
    Thus, it is impossible to have this congruent to 0 mod 3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Help!
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: June 28th 2011, 10:41 PM
  2. [SOLVED] Congruence
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: June 26th 2010, 12:01 PM
  3. Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 6th 2010, 06:50 AM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 15th 2009, 12:12 PM
  5. congruence
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 22nd 2008, 09:03 PM

Search Tags


/mathhelpforum @mathhelpforum