Results 1 to 3 of 3

Math Help - gcd odd and even proof

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    179
    Thanks
    1

    gcd odd and even proof

    Show that if m does not = n then

    gcd((a^2)^n) + 1, ((a^2)^m + 1) = 1, if a is even
    and 2, if a is odd.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Formulation?

    Not sure if this question is formulated correctly. I am reading:

    For all m\neq n, gcd(a^{2m}+1,a^{2n}+1)=\begin{cases}1 & \text{a even} \\2 & \text{a odd} \\ \end{cases}

    This would mean that for a even, any two elements in the sequence c(a)_k=a^{2k}+1 should be relatively prime without exception: c(2)=\{5,17,65,257,1025,4097,16385,...\}. As you can see, the conjecture is simply wrong.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Exponents not Associative

    Theorem: WLOG, for <br /> <br />
m> n, \gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases}1 & \text{a even} \\2 & \text{a odd} \\ \end{cases}<br />

    Proof: Start by noticing a^{2^n}+1|a^{2^m}-1 -- see proof at http://www.mathhelpforum.com/math-he...s-2-n-1-a.html. So we can rewrite as \gcd(kx+2,k), for k=a^{2^n}+1 and some x. It can be easily seen that k has the opposite parity of a. So if a is even, k is odd, and \gcd(kx+2,k)=1. If a is odd, k is even, and \gcd(kx+2,k)=2. QED
    Last edited by Media_Man; November 7th 2009 at 04:00 AM. Reason: inserted link
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum