Results 1 to 2 of 2

Math Help - help with proof for number theory, possibly using induction?

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Los Angeles
    Posts
    2

    help with proof for number theory, possibly using induction?

    If k > 2, and n = 2k-3, show that 3n is not congruent to 1 (mod 2k).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie LordoftheFlies's Avatar
    Joined
    Dec 2012
    From
    Paris, France
    Posts
    10
    Thanks
    4

    Re: help with proof for number theory, possibly using induction?

    Old thread but if you're still interested: there are several ways to do this.

    1) By induction for n>2: assume 3^{2^{n-3}}\equiv 2^{n-1}+1\pmod{2^n}\iff 3^{2^{n-3}}= 2^{n-1}+1+2^{n}k

    \Rightarrow\;\; 3^{2^{n-2}}= (2^{n-1}+1+2^{n}k)^2=2^n+1+2^{n+1}(2^{n-3}+2^{n-1}k+2^{n-1}k^2)

    \iff 3^{2^{n-2}}\equiv 2^{n}+1\pmod{2^{n+1}} etc.

    2) A rather nice way is to consider 3^{2^{n-3}}-1=(3^2-1)(3^2+1)(3^4+1)\cdots (3^{2^{n-4}}+1)=2^3 \cdot\displaystyle\prod_1^{n-4} (3^{2^k}+1)
    3^2\equiv 1\pmod{4}\Rightarrow 3^{2^k}\equiv 1\pmod{4}\Leftrightarrow 3^{2^k}+1\equiv 2\pmod{4} therefore the highest power of 2 dividing 3^{2^k}+1 is 2

    It follows that 2^{n-1} is the highest power of 2 dividing \displaystyle 2^3\cdot \prod_1^{n-4} (3^{2^k}+1), so 2^n cannot divide 3^{2^{n-3}}-1
    Last edited by LordoftheFlies; January 1st 2013 at 11:45 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: May 7th 2012, 12:23 PM
  2. induction..prime number proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 08:47 AM
  3. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2009, 03:09 PM
  4. Lucas Number Proof By Induction
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 16th 2008, 04:08 PM
  5. Number theory, divisibility, mathematical induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 12th 2006, 11:29 PM

Search Tags


/mathhelpforum @mathhelpforum