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.

    --
    Edit:
    [*] 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Euler totient puzzle
  1. A Puzzle (Replies: 29)

Loading...