wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> "Politically correct" moduli re x^2+x-2
        
(Message started by: ecoist on May 29^th, 2007, 7:33pm)

Title: "Politically correct" moduli re x^2+x-2
Post by ecoist on May 29^th, 2007, 7:33pm

A positive integer n is politically correct relative to the polynomial P(x)=x²+x-2 if the congruence P(x)=0 (mod n) has at most two incongruent solutions modulo n. For n=18, P(x)=0 (mod 18 ) has the three incongruent solutions 1, 4, and 7 mod 18. So 18 comes up short on sensitivity. Find all politically correct positive integers n relative to the polynomial P.

(Sorry, guys. x²+x+1 was a bad choice.)

Title: Re: "Politically correct" moduli re x^2+
Post by Eigenray on May 30^th, 2007, 11:30am

I think x²+x+1 makes it more interesting. In that case, the politically correct moduli are:

(0) n divisible by 9 or some prime which is 2 mod 3
(1) n = 1, 3
(2) n = p^k, 3p^k, where p is 1 mod 3, k>0.

Title: Re: "Politically correct" moduli re x^2+
Post by Eigenray on May 30^th, 2007, 11:55am

Say n is politically correct in degree d if for all monic integral polynomials P of degree d, P(x)=0 has at most d roots mod n.

The only n>1 which are politically correct in degree 2 are the primes and n=4. In fact, these n are politically correct in every degree.