Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler totient puzzle

  1. Mar 16, 2012 #1
    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. jcsd
  3. Mar 17, 2012 #2
    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 [itex]k \equiv -n \pmod {p_n}[/itex] 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.

    [*] Well, not any, but you get the idea.
    Last edited: Mar 17, 2012
  4. Mar 17, 2012 #3
    You are right.
    Thanx for your solution.
    Anyway it does not mean that it ALWAYS exists k for every n odd prime.
    Proof is needed.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook