# Euler totient puzzle

1. Mar 16, 2012

### Gaussianheart

Let n=79
phi is Euler totient

Can you find a number k such as :

phi(k)=0 mod 79
phi(k+1)=0 mod 79
phi(k+2)=0 mod 79
phi(k+3)=0 mod 79
.....
phi(k+78)=0 mod 79
phi(k+79)=0 mod 79

Good luck!

2. Mar 17, 2012

### dodo

Since there are infinite primes in any[*] arithmetic sequence, I'd choose 80 primes, call them p0 to p79, of the form 79n+1.

Next, use the Chinese Remainder Theorem to find a solution 'k' of the system of 80 congruences $k \equiv -n \pmod {p_n}$ with n=0,1,2,...79.

It follows that p0 divides k, p1 divides k+1, ... and p79 divides k+79. Then each (pn-1) will divide each phi(k+n); and since all primes were a multiple of 79 plus 1, each phi(k+n) will be divisible by 79, as required.

--
Edit:
[*] Well, not any, but you get the idea.

Last edited: Mar 17, 2012
3. Mar 17, 2012

### Gaussianheart

You are right.