
Euclid Numbers
We can define Euclid numbers, e(n), by the following inductive definition:
e(1) = 2
e(n) = e(1) *...*e(n1) + 1, n > 1
Calculating, we get
e(1) = 2
e(2) = e(1) + 1 = 2+1 =3
e(3) = e(1) * e(2) + 1 = 2*3+1 =7
e(4) = e(1) * e(2) * e(3) + 1 = 2*3*7+1 =43
Show that,
(i) when j /= k ( '/=' is supposed to mean 'NOT equal to!), e(j) and e(k) are
relatively prime, i.e. gcd(e(j), e(k)) = 1
(ii) for n > 0,
e(n+1) = (e(n))^{2 } e(n) + 1
No idea how to do (i), tried (ii) using induction but didn't get very far. Please help, would
be ever so grateful!!!

Re: Euclid Numbers
(ii) should be done using induction.
e(n+1) = e(1)*...*e(n1)*e(n) + 1
= (e(n)1)*e(n) + 1
= e(n)*e(n)  e(n) + 1 which is what you are required to prove.

Re: Euclid Numbers