Author 
Topic: "Politically correct" moduli re x^2+x2 (Read 890 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


"Politically correct" moduli re x^2+x2
« on: May 29^{th}, 2007, 7:33pm » 
Quote Modify

A positive integer n is politically correct relative to the polynomial P(x)=x^{2}+x2 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^{2}+x+1 was a bad choice.)

« Last Edit: May 29^{th}, 2007, 8:34pm by ecoist » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: "Politically correct" moduli re x^2+
« Reply #1 on: May 30^{th}, 2007, 11:30am » 
Quote Modify

I think x^{2}+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.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: "Politically correct" moduli re x^2+
« Reply #2 on: May 30^{th}, 2007, 11:55am » 
Quote Modify

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.


IP Logged 



