wu :: forums
« wu :: forums - Roots of a polynomial in a finite field... »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 7:52am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Icarus, SMQ, towr, william wu, Grimbal, Eigenray, ThudnBlunder)
   Roots of a polynomial in a finite field...
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Roots of a polynomial in a finite field...  (Read 382 times)
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Roots of a polynomial in a finite field...  
« on: Aug 5th, 2015, 7:54pm »
Quote Quote Modify Modify

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?
 
 
 
IP Logged

Regards,
Michael Dagg
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Roots of a polynomial in a finite field...  
« Reply #1 on: Aug 5th, 2015, 11:24pm »
Quote Quote Modify Modify

by trial an error n=10, with roots x=2,3,7,8
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
0.999...
Full Member
***





   


Gender: male
Posts: 156
Re: Roots of a polynomial in a finite field...  
« Reply #2 on: Aug 6th, 2015, 6:44pm »
Quote Quote Modify Modify

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 x(x+1), when n>6.
 
The easiest case to consider is when n=2ep, where p is an odd prime. Here, we have 4 roots if and only if e>0, because by the Chinese Remainder Theorem there is a unique x such that x=-1(mod p) and x=0(mod 2e). Similarly, there is a unique x satisfying x=1(mod p) and x=0(mod 2e).
 
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 2em, and there may (could potentially) exist (exactly 2 distinct) factorizations of m as k1k2 such that 2ek1+/-1=k2 and it seems to be challenging to determine precisely when this occurs.
 
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board