Results 1 to 3 of 3

Math Help - Help proving the following theorems

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    United States
    Posts
    1

    Help proving the following theorems

    1. For all natural numbers n, gcd (n, n +1) = 1
    2. Let k be a natural number. Then there exists a natural number n (which will be much larger than k) such that no natural number less than k and greater than 1 divides n.
    3. Let k be a na be a natural number. Then there exists a prime number larger than k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,475
    Thanks
    956

    Re: Help proving the following theorems

    1) https://answers.yahoo.com/question/i...3060209AATMHTv

    2) follows almost immediately from (1)

    3) follows immediately from (2)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Help proving the following theorems

    Suppose n = dk, and n+1 = dm.

    We have: 1 = (n+1) - n = dm - dk = d(m - k).

    Since n+1 > n, dm > dk, so m > k. Thus d, m-k > 0 are both positive divisors of 1.

    The only possibility is, therefore, that d = 1, and m-k = 1.

    Since ANY common divisor of n and n+1 is equal to 1, the greatest such divisor is (of necessity) 1.

    If you use the Bezout identity definition: that gcd(a,b) = min({ra+sb > 0: r,s integers}), we see that: (1)(n+1) + (-1)(n) = 1, so that it is immediate that gcd(n,n+1) = 1 (since this is the smallest positive integer).

    For (2) we can use "Euclid's trick":

    consider n = (1*2*....*k)+1.

    Every number less than k divides n-1 = 1*2*...*k, but if a natural number r divides n-1, and divides n, we have r divides gcd(n-1,n). Now apply part(1) (using "n-1" in place of "n").

    To prove (3) assume the contrary, that there is no prime number larger than k. Now use the same trick as in part (2), to show that the number we used there is not divisible by any prime, and thus....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Theorems
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 18th 2012, 02:03 PM
  2. Proving Theorems with Axioms
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 16th 2011, 06:36 PM
  3. [SOLVED] 2 ordered field theorems that need proving
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 15th 2011, 06:17 PM
  4. Replies: 1
    Last Post: November 17th 2010, 11:41 PM
  5. Need help proving a couple theorems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 20th 2009, 11:09 PM

Search Tags


/mathhelpforum @mathhelpforum