wu :: forums - Print Page


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

        riddles >> medium >> Roots of a polynomial in a finite field...
        
(Message started by: Michael Dagg on Aug 5^th, 2015, 7:54pm)

Title: Roots of a polynomial in a finite field...
Post by Michael Dagg on Aug 5^th, 2015, 7:54pm

Let Z_n be the ring of integers modulo n > 6.

What is the smallest n for which the quadratic polynomial
x^2 - 5x + 6 has four distinct roots?

Title: Re: Roots of a polynomial in a finite field...
Post by towr on Aug 5^th, 2015, 11:24pm

by trial an error [hide]n=10, with roots x=2,3,7,8[/hide]

Title: Re: Roots of a polynomial in a finite field...
Post by 0.999... on Aug 6^th, 2015, 6:44pm

Nice to see you around, Michael Dagg.

So we start with the factorization (x-3)(x-2), and note that there is a one-to-one correspondence between the roots of the provided polynomial and the roots of [hide]x(x+1)[/hide], when n>6.

The easiest case to consider is when n=2^ep, where p is an odd prime. Here, we have 4 roots if and only if [hide]e>0, because by the Chinese Remainder Theorem there is a unique x such that x=-1(mod p) and x=0(mod 2^e). Similarly, there is a unique x satisfying x=1(mod p) and x=0(mod 2^e).[/hide]

This is enough to resolve the problem as stated, but why not try for a classification of all n for which there are 4 roots.

The stumbling block is that n may take the form 2^em, and there may (could potentially) exist [hide](exactly 2 distinct) factorizations of m as k₁k₂ such that 2^ek₁+/-1=k₂[/hide] and it seems to be challenging to determine precisely when this occurs.