
Number Theory Number Theory Math Forum 
 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 ? 
April 13th, 2011, 07:55 PM  #2 
Global Moderator 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). 
April 13th, 2011, 09:38 PM  #3 
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)(xx1)(xx2)...(xxt)(mod p) (Here some xi could be same) Any for any integer a, (g(a),p)=1. So pf(a) iff p(ax1)(ax2)...(axt) So p^kf(a) => pf(a)=>p(ax1)(ax2)...(axt) => a = xi(mod p) for some i. Let f(x)g(x)(xx1)(xx2)...(xxt)=p*u(x) Now let's take a look for x=y*p+x1, if p^2f(y*p+x1) so p^2g(y*p+x1)*y*p*(y*p+x1x2)...(y*p+x1xt)+p*u(y*p+x1) so pg(y*p+x1)*y*(y*p+x1x2)...(y*p+x1xt)+u(y*p+x1)=g(x1)*y*(x1x2)...(x1xt)+u(x1) so if x1 is different from x2,...,xt, We only have a unique y to reach the condition p^2f(y*p+x1) And similiar, we could prove that there're exact t solutions for p^kf(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^2f(y*p+x1) => pu(x1). So either there're no correspondent solutions for p^2f(y*p+x1) or all y are solutions. So in worse case, we may have p^{k1} solutions. Such as if f(x)=(x1)^k, for any a=1(mod p), p^kf(a). 
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??? 
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 (padic) 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:
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)=(xa)^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  

Tags 
modulo, number, solutions, squared 
Search tags for this page 
modulo prime squared,hensel lemma proof,square root modulo p SQUARED,polynomial modulo the square of a prime
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 nonnegative 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 