pairwise relatively prime

Printable View

June 10th 2010, 05:45 AM
aman_cc

pairwise relatively prime

This question is based on Goldbach's Proof of the Infinitude of Primes
Goldbach's Proof of the Infinitude of Primes (1730)

Let
a1 = a
a2 = a1+b
a3 = a1a2 + b
a4 = a1a2a3 + b
..
..

Prove that the above seq is paiwise prime (given HCF(a,b) = 1)

My attempt
If the assertion is not true then their exist a smallest number 'n' for which a_n is not relatively with some a_m (m>n)

Thus there exist a prime p such that
p|a_m
and p|a_n

=> p|a_m - a_n
=> p|a1a2a3....a_(n-1) [a_n....a_(m-1) - 1]
Now p can't divide [a_n....a_(m-1) - 1] (as p|a_n)

Thus p|a1a2a3....a_(n-1)
=> p|ai where i < n

Hence 'n' is not the smallest. Hence Proved

I have two questions

1. Can someone please review this proof for me?
2. Can someone suggest a proof without using induction?
June 10th 2010, 08:32 AM
undefined

Quote:

Originally Posted by aman_cc

This question is based on Goldbach's Proof of the Infinitude of Primes
Goldbach's Proof of the Infinitude of Primes (1730)

Let
a1 = a
a2 = a1+b
a3 = a1a2 + b
a4 = a1a2a3 + b
..
..

Prove that the above seq is paiwise prime (given HCF(a,b) = 1)

My attempt
If the assertion is not true then their exist a smallest number 'n' for which a_n is not relatively with some a_m (m>n)

Thus there exist a prime p such that
p|a_m
and p|a_n

=> p|a_m - a_n
=> p|a1a2a3....a_(n-1) [a_n....a_(m-1) - 1]
Now p can't divide [a_n....a_(m-1) - 1] (as p|a_n)

Thus p|a1a2a3....a_(n-1)
=> p|ai where i < n

Hence 'n' is not the smallest. Hence Proved

I have two questions

1. Can someone please review this proof for me?
2. Can someone suggest a proof without using induction?

1. You forgot to include the case n=1. Also I'm wondering if special consideration should be made for the case a=1, since it could lead to a contradiction of the form p|1. But otherwise I agree with your proof.

2. Your proof did not use induction, but rather well ordering of the naturals.
June 10th 2010, 08:44 AM
aman_cc

Quote:

Originally Posted by undefined

1. You forgot to include the case n=1. Also I'm wondering if special consideration should be made for the case a=1, since it could lead to an earlier contradiction of the form p|1. But otherwise I agree with your proof.

2. Your proof did not use induction, but rather well ordering of the naturals.

n=1 ; I omitted it as I thought it is trivial to prove that. Sorry for that.

a =1; as far as i can think i dont think we need any special treatment.

regarding your point 2 - i consider induction and well ordering as one and the same, so i am still looking at another way to prove this. thanks
June 10th 2010, 08:58 AM
undefined

Quote:

Originally Posted by aman_cc

n=1 ; I omitted it as I thought it is trivial to prove that. Sorry for that.

a =1; as far as i can think i dont think we need any special treatment.

regarding your point 2 - i consider induction and well ordering as one and the same, so i am still looking at another way to prove this. thanks

Well we could use a proof just like the one on the page you linked to, but then we'd have to prove that gcd(a_i, b)=1 for all i. My instinct is to use induction for that... can't think of anything that doesn't.