Author |
Topic: Roots of a polynomial in a finite field... (Read 398 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Roots of a polynomial in a finite field...
« on: Aug 5th, 2015, 7:54pm » |
 Quote  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:
Posts: 13730
|
|
Re: Roots of a polynomial in a finite field...
« Reply #1 on: Aug 5th, 2015, 11:24pm » |
Quote 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:
Posts: 156
|
|
Re: Roots of a polynomial in a finite field...
« Reply #2 on: Aug 6th, 2015, 6:44pm » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print