# Math Help - Euclid Numbers

1. ## Euclid Numbers

We can define Euclid numbers, e(n), by the following inductive definition:

e(1) = 2
e(n) = e(1) *...*e(n-1) + 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!!!

2. ## Re: Euclid Numbers

(ii) should be done using induction.
e(n+1) = e(1)*...*e(n-1)*e(n) + 1
= (e(n)-1)*e(n) + 1
= e(n)*e(n) - e(n) + 1 which is what you are required to prove.

3. ## Re: Euclid Numbers

Thanks coolge!