My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
April 13th, 2011, 07:27 PM   #1
Newbie
 
Joined: Mar 2011

Posts: 10
Thanks: 0

Number of solutions modulo p squared

When we have a polynomial f(x) = 0 modulo I know that using the Chinese Remainder Theorem, the maximum number of solutions is:
the product of the maximum number of solutions for f(x) = 0 mod .
which is the degree of the polynomial f(x).
then here we have at most k*deg(f) solutions

However, in the case we are modulo , I am wondering how I can find the maximum numbers of solutions for f(x) = 0 modulo ?
fortin946 is offline  
 
April 13th, 2011, 07:55 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Number of solutions modulo p squared

If p = 2 the maximum is 4. If p is an odd prime then the maximum is 2.

Edit: Sorry, I'm thinking of a different problem here (square root mod p^k).
CRGreathouse is offline  
April 13th, 2011, 09:38 PM   #3
duz
Senior Member
 
Joined: Oct 2008

Posts: 215
Thanks: 0

Re: Number of solutions modulo p squared

To analysis f(x)=0(mod p^k)
we could first find all solutions of f(x)=0(mod p).
If all the solutions are x1,x2,...,xt, so we have f(x)=g(x)(x-x1)(x-x2)...(x-xt)(mod p) (Here some xi could be same)
Any for any integer a, (g(a),p)=1.
So p|f(a) iff p|(a-x1)(a-x2)...(a-xt)
So p^k|f(a) => p|f(a)=>p|(a-x1)(a-x2)...(a-xt) => a = xi(mod p) for some i.
Let f(x)-g(x)(x-x1)(x-x2)...(x-xt)=p*u(x)
Now let's take a look for x=y*p+x1, if p^2|f(y*p+x1)
so
p^2|g(y*p+x1)*y*p*(y*p+x1-x2)...(y*p+x1-xt)+p*u(y*p+x1)
so
p|g(y*p+x1)*y*(y*p+x1-x2)...(y*p+x1-xt)+u(y*p+x1)=g(x1)*y*(x1-x2)...(x1-xt)+u(x1)
so if x1 is different from x2,...,xt, We only have a unique y to reach the condition p^2|f(y*p+x1)
And similiar, we could prove that there're exact t solutions for p^k|f(x) when x1,x2,...,xt are all different.
But if any solutions are duplicated, such as x1=x2, it will be more complex
For example, now
p^2|f(y*p+x1) => p|u(x1). So either there're no correspondent solutions for p^2|f(y*p+x1) or all y are solutions.
So in worse case, we may have p^{k-1} solutions. Such as if f(x)=(x-1)^k, for any a=1(mod p), p^k|f(a).
duz is offline  
April 17th, 2011, 02:24 PM   #4
Newbie
 
Joined: Mar 2011

Posts: 10
Thanks: 0

Re: Number of solutions modulo p squared

Actually I was looking for something simpler. For instance, consider a polynomial of degree 3 over Z/49Z.
Since, , then we consider first the solutions over Z/7Z.
There are at most 3 solutions since the degree of the polynomial is 3.
We want to lift these solutions to the ring Z/49Z. . My idea is then to use Hensel's lemma.
The truth is that there are at most 8 solutions in Z/49Z. Why???
fortin946 is offline  
April 18th, 2011, 08:21 AM   #5
Senior Member
 
Joined: Sep 2008

Posts: 150
Thanks: 5

Re: Number of solutions modulo p squared

Hi all!

As this is a bit longer than intended here is the outline: I give the solution for the case k=2, then I give the prove of this solution, which gives a strong indication towards a formula in the general case. I give this formula (and the reasoning that leads to it) as a conjecture in the last paragraph.

Let me first make a remark, to fix the exact parameters of the problem:
I will assume that the coefficients of the polynomial are (p-adic) integers and look at them modulo different powers of p. In addition we should assume the polynomial to be normalized (i.e., leading coefficient=1), otherwise we get the maximal number of solutions: is satisfied by all numbers mod and even if we assume the degree to be defined modulo p^k ( that would make the last example the zero polynomial) we could still take which has degree one and solutions namely all multiples of p.

Now to your problem:

Quote:
Originally Posted by fortin946
Actually I was looking for something simpler. For instance, consider a polynomial of degree 3 over Z/49Z.
Since, , then we consider first the solutions over Z/7Z.
There are at most 3 solutions since the degree of the polynomial is 3.
We want to lift these solutions to the ring Z/49Z. . My idea is then to use Hensel's lemma.
The truth is that there are at most 8 solutions in Z/49Z. Why???
The short answer is: Because 8=7+1 and in general a polynomial of degree 3 will have at most p+1 solutions mod p^2. (Plus, there is allways one that has exactly this number, for instance ) more generally a polynomial of degree has at most solutions mod and one of degree has at most solutions. Moreover this number will allways be achieved provided p is big enough namely greater equal n in the first case and greater equal n+1 in the second place.

A proof of this statement actually involves Hensel's Lemma: First decompose your polynomial modulo p as where all the are different mod p and h does not have any zero mod p. Now (the general version of) Hensel's lemma tells us, that we can find a factorization of f in such that and . As all the elements of that do not map to zero in are units it is easy to check, that x is a zero of f mod iff it is a zero for some mod . Thus we have reduced our problem to the case of the polynomials, which are powers of linear polynomials mod p.

I would have to think a bit more about the general case but it is clear, that a polynomial which is congruent to modulo p can have at most zeros mod p^k namely those numbers which are congruent to a modulo p. Conversely there are polynomials of this form, which have solutions (where [] is the floor function): simply take f(x)=(x-a)^n even before reducing mod p. This finishes the case, where k=2 as upper and lower bound agree for all (and are in fact equal to p there) and for degree one polynomials we have always exactly one solution. So the best bet in the k=2 case is to take as many degree two factors as you can (each of which gives p zeros) and at most one smaller factor which is then of degree 1 and gives one additional zero.

Now in general i think, that is actually the best number of zeros you can get from one factor. And some combinatorics should show, that the best distribution, is to max out all the factors and have one for the rest. So writing with s<r my conjecture is that there are at most zeros mod p^k for a degree d polynomial and we get that many zeros for at least one polynomial as soon as p>s.

best rgds
Peter
Peter is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
modulo, number, solutions, squared



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Negative number squared scarecr0w132 Elementary Math 3 February 24th, 2014 08:19 AM
Large number modulo FloorPlay Number Theory 2 October 30th, 2013 08:59 PM
Number of all non-negative solutions. Bolt Algebra 7 July 31st, 2011 07:06 AM
Why primes number when doing modulo? niravshah99 Number Theory 4 June 20th, 2010 02:53 AM
number of solutions. earth Math Events 3 July 8th, 2009 09:14 PM





Copyright © 2019 My Math Forum. All rights reserved.