Tutorial for Quadratic Equations 
Here is a nice tutorial for the problem Quadratic Equations courtesy Neelesh Bodas
Introduction:
This tutorial discusses one of the “hard problems” of the July Contest  Quadratic Equations. I called this problem “hard” because it is placed in the “hard problems” category and there were only 5.25% successful submissions for this problem. However, I believe this was actually one of the easy problems in this competition – provided you knew a little bit of number theory. Here are some very basic examples of quadratic equations in general and the computation of discriminant and roots of such equations. Observe the inverted parabola for negative values of "a" and mouthopen parabola for positive values of 'a'. Let’s see how.
To begin with, let’s get rid of all the verbosity from the problem statement and understand what the problem actually asks. In simplest terms, the problem asks us to find all possible values of w such that (Aw^{ 2 } +Bw+C) is divisible by prime P. In mathematical terms, the task is to find all possible solutions for the congruence:
With Constraints: 0 < A < P, 0 ≤ w, B, C < P < 10^{6}. Incidentally, if you are a number theory fan, chances are that you already know the answer to this problem. Typically this scenario would be discussed in almost every number theory book, and is usually covered under the heading quadratic residues Before we go into the detailed solution, let’s jot down few basic points first –
Constraints: P is prime, 0 < M,N,w < P
Let’s take a simple example to understand this case. Let M = 4, N = 3 and P = 11. The following table lists the required values
The first column lists all possible values of “w mod P” and the other two columns represent the corresponding values for “(Mw) mod P” and “(MwN) mod P” respectively. Observe that no values seem to be repeated in second or third column. In other words, it looks like all values of “(Mw) mod P” are different when w belongs to the set {0,1,…,P1}.
It is easy to see that this observation will always hold. To see why, suppose there are two distinct values of w, say w1 and w2, with 0 ≤ w2 < w1 < P, such that Mw1 ≡ k (mod P) and Mw2 ≡ k (mod P) for some k. This would imply that Mw1 ≡ Mw2(mod P), which means P  M(w1w2), which in turn means P  (w1w2) : a contradiction since P > w1 > w2 ≥ 0. Thus we see that every entry in column2 will be different (and each entry will be between 0 to P1 inclusive). As there are exactly P entries in column 2, this means that every entry in the set {0,1,…,(p1)} will occur exactly once in column2. Consequently, there would be exactly one value of w which would evaluate to N in column2. In fact, this is the value of w that we are looking for, since this is the only value that satisfies Mw ≡ N (mod P). (Applying this argument to the example above, we would return w = 9 as our answer to the congruence Mw ≡ N (mod P)). Moral of the story – The linear congruence Mw ≡ (mod P) with 0<M,N<P has exactly one solution. And the good news is that it is not at all difficult to find what this solution would be. Let w = k represent this solution. Then we have: Mk ≡ N (mod P) i.e. (Mk – N = Pu) for some integer u. Rearranging the terms, we get Mk + P(u) = N. Observe that since GCD of M and P is 1, Bézout's identity guarantees existence of integers x and y such that Mx+Py=1. A quick google search would reveal that the Extended Euclid’s Algorithm can be used to get values of x and y. Detailed implementation of Extended Euclid’s algorithm is easily available on the web and hence left as a (trivial) exercise to the reader. Once we get x, observe that k = xN. Of course, make sure to adjust the value of xN (if needed) to bring it in the set {0,1,…,P1}. The solution to the equation (B) can then be obtained by plugging values M = A and N = B in the above discussion. Similarly solution of (E) can be obtained by plugging M = 2A and N = uB in the above discussion.
Constraints: P is prime, 0 < M,N,w < P
Since the tableapproach worked in the previous case, let’s use the same again.With M = 4, N = 3 and P = 11, we get following results:
Observe that unlike the previous table, the columns in this table don’t have all the values. Taking an example of second column (w^{2}mod P ), we see that some values (like 2) are not present, whereas some other values (like 4) are repeated. More specifically –
For example, with m = 9 and n = 15, observe that x = 12 satisfies this congruence, and hence we say that 9 is a quadratic reside modulo 15. Similarly, 4 is also a quadratic residue modulo 15, since x = 2 satisfies the congruence x^{2}≡4(mod 15). On the other hand, there is no x for which x^{2}≡11(mod 15), and hence 11 is a “quadratic nonresidue” modulo 15. As another example, observe that 0,1 and 4 are the only quadratic residues modulo 8. Interestingly, note that it is only the terminology that is new here  the underlying concept is very much close to what most of us would have already studied (hopefully!). For example, we all know that every square is of the form 4k or 4k+1. (Proof is trivial, left as an exercise to the reader). This means that x^{2}≡v(mod 4) has a solution only when v = 0 or 1. In other words, the only quadratic residues modulo 4 are 0 and 1. Taking another example, we (definitely) know that a square always end in 0,1,4,5,6 or 9. That is to say, the congruence x^{2}≡v(mod 10) has a solution only when v belongs to the set {0,1,4,5,6,9}. Stated differently, the set of quadratic nonresidues modulo 10 is {2,3,7,8}. Thus, in the simplest terms – A number m is a called as quadratic residue mod n if a square can take the form (nk+m) for some integer k. Finally observe that in the current case, we are only interested in finding quadratic residues modulo a prime number. More specifically, we want to find –
Aw^{2}+Bw+C ≡ 0 (mod P)
 [A]
With Constraints: 0 < A < P, 0 ≤ w, B, C < P < 10^{6}. Incidentally, if you are a number theory fan, chances are that you already know the answer to this problem. Typically this scenario would be discussed in almost every number theory book, and is usually covered under the heading quadratic residues Before we go into the detailed solution, let’s jot down few basic points first –
 Can a bruteforce solution work? (In almost all programming problems, it becomes very important to understand whether or not the bruteforce solution would work without actually writing the code and testing it out. Of course in most of the problems it wouldn’t work.). In the current case, since there are about 10000 test cases and each test case would need 10^{6} iterations in the worst case, the total number of iterations would be 10^{10}. Convince yourself that an empty loop that runs 10^{10} times needs much more time than 3 seconds. The bruteforce approach thus gets ruled out.
 Observe that since w < P, smaller cases with lower values of P are very easy to handle. For example, when P=2, the only values that w may take are 0 and 1. Similarly when P=3, the only allowed values for w are 0,1 and 2. Thus we can use the bruteforce approach for smaller values of P, like 2, 3,5 etc.
 Since B and C can be zero, it makes sense to deal with these cases separately, as the problem could reduce to a lesscomplicated version in these cases. Observe that:
 If B=C=0, then the problem reduces to finding all w such that P  (Aw^{2}).Since 0 < A < P and 0 ≤ w < P, the only solution is w = 0.
 If C=0 but B≠0, then the problem reduces to finding all w such that w*(Aw+B) ≡ 0 (mod P). Since P is prime, this implies that Pw or P(Aw+B). Clearly, w = 0 is one solution, and other solutions would be obtained by solving the linear congruence
Aw+B ≡ 0 (mod P) [B]
Thus observe that in this case we have reduced the problem of solving a quadratic congruence to solving a linear congruence.  If B=0 but C≠0 then the problem reduces to finding all w such that
Aw^{2}+C ≡ 0 (mod P) [C]
Again observe that we have a special case of quadratic congruence here, which doesn’t have any linear term.
 In fact, the original congruence in [A] can always be reduced to a form similar to [C] even in the most general case, when 0 < A,B,C < P. The trick is to do the “square completion”. Observe that we can rewrite [A] as:
A^{2}w^{2}+4ABw+4AC+B^{2}B^{2} ≡ 0 (mod P) ⇔ (2Aw+B)^{2}+(4ACB^{2}) ≡ 0 (mod P) Let u=2Aw+B and D=(4ACB^{2}). Then the congruence can be rewritten as: u^{2} + D ≡ 0 (mod P) Of course, if u or D are not between 0 to P1, then can be changed modulo P to bring them in the required range.Thus, the most general case of [A] needs a twostep solution:
 Solve the following quadratic congruence for u:
u^{2}+(4ACB^{2}) ≡ 0 (mod P) [D]
 Solve the following linear congruence for w:
(2Aw+B) ≡ u (mod P)i.e. 2Aw ≡ (uB) (mod P) [E]where u is the solution obtained in step (1).
 Solve the following quadratic congruence for u:
Solving linear congruences:
Task: Find all possible solutions to the congruence Mw ≡ N (mod P)
Constraints: P is prime, 0 < M,N,w < P
Let’s take a simple example to understand this case. Let M = 4, N = 3 and P = 11. The following table lists the required values
w mod P  (Mw) mod P  (Mw – N) mod P

0  0  8 
1  4  1 
2  8  5 
3  1  9 
4  5  2 
5  9  6 
6  2  10 
7  6  3 
8  10  7 
9  3  0 
10  7  4 
It is easy to see that this observation will always hold. To see why, suppose there are two distinct values of w, say w1 and w2, with 0 ≤ w2 < w1 < P, such that Mw1 ≡ k (mod P) and Mw2 ≡ k (mod P) for some k. This would imply that Mw1 ≡ Mw2(mod P), which means P  M(w1w2), which in turn means P  (w1w2) : a contradiction since P > w1 > w2 ≥ 0. Thus we see that every entry in column2 will be different (and each entry will be between 0 to P1 inclusive). As there are exactly P entries in column 2, this means that every entry in the set {0,1,…,(p1)} will occur exactly once in column2. Consequently, there would be exactly one value of w which would evaluate to N in column2. In fact, this is the value of w that we are looking for, since this is the only value that satisfies Mw ≡ N (mod P). (Applying this argument to the example above, we would return w = 9 as our answer to the congruence Mw ≡ N (mod P)). Moral of the story – The linear congruence Mw ≡ (mod P) with 0<M,N<P has exactly one solution. And the good news is that it is not at all difficult to find what this solution would be. Let w = k represent this solution. Then we have: Mk ≡ N (mod P) i.e. (Mk – N = Pu) for some integer u. Rearranging the terms, we get Mk + P(u) = N. Observe that since GCD of M and P is 1, Bézout's identity guarantees existence of integers x and y such that Mx+Py=1. A quick google search would reveal that the Extended Euclid’s Algorithm can be used to get values of x and y. Detailed implementation of Extended Euclid’s algorithm is easily available on the web and hence left as a (trivial) exercise to the reader. Once we get x, observe that k = xN. Of course, make sure to adjust the value of xN (if needed) to bring it in the set {0,1,…,P1}. The solution to the equation (B) can then be obtained by plugging values M = A and N = B in the above discussion. Similarly solution of (E) can be obtained by plugging M = 2A and N = uB in the above discussion.
Solving quadratic congruences:
Task: Find all possible solutions to the congruence Mw^{2} ≡ N (mod P) Constraints: P is prime, 0 < M,N,w < P
Since the tableapproach worked in the previous case, let’s use the same again.With M = 4, N = 3 and P = 11, we get following results:
w mod P  w^{2}mod P  (Mw^{2})mod P  (Mw^{2}N)mod P 
0  0  0  8 
1  1  4  1 
2  4  5  2 
3  9  3  0 
4  5  9  6 
5  3  1  9 
6  3  1  9 
7  5  9  6 
8  9  3  0 
9  4  5  2 
10  1  4  1 
 if we ignore the starting 0 in this column, then the column looks symmetric – The values 1,4,9,5,3 repeat in the reverse order.
 All values in the first half of this column are distinct.
 Observe that (Pw)^{2} ≡ w^{2} (mod P). Thus, for any w, numbers w^{2} and (Pw)^{2} would evaluate to the same result mod P. This means that the column (Mw^{2} mod P) would always be symmetric around the center.
 To see why all the values in the first half of the column would be distinct, let us assume that two values of w, say w1 and w2, (WLG let w1 > w2) both occurring in the set {0,1,…,(P1)/2} evaluate to the same result in column2, i.e., let Mw1^{2} ≡ Mw2^{2} (mod P). This would mean that P(w1^{2}w2^{2}), which would in turn mean P(w1+w2) or P(w1w2). But this is clearly a contradiction, as both (w1+w2) and (w1w2) are less than P but greater than zero.
 How do we know whether Mw^{2} ≡ N (mod P) has a solution or not?
 If there is a solution, how do we find it?
For example, with m = 9 and n = 15, observe that x = 12 satisfies this congruence, and hence we say that 9 is a quadratic reside modulo 15. Similarly, 4 is also a quadratic residue modulo 15, since x = 2 satisfies the congruence x^{2}≡4(mod 15). On the other hand, there is no x for which x^{2}≡11(mod 15), and hence 11 is a “quadratic nonresidue” modulo 15. As another example, observe that 0,1 and 4 are the only quadratic residues modulo 8. Interestingly, note that it is only the terminology that is new here  the underlying concept is very much close to what most of us would have already studied (hopefully!). For example, we all know that every square is of the form 4k or 4k+1. (Proof is trivial, left as an exercise to the reader). This means that x^{2}≡v(mod 4) has a solution only when v = 0 or 1. In other words, the only quadratic residues modulo 4 are 0 and 1. Taking another example, we (definitely) know that a square always end in 0,1,4,5,6 or 9. That is to say, the congruence x^{2}≡v(mod 10) has a solution only when v belongs to the set {0,1,4,5,6,9}. Stated differently, the set of quadratic nonresidues modulo 10 is {2,3,7,8}. Thus, in the simplest terms – A number m is a called as quadratic residue mod n if a square can take the form (nk+m) for some integer k. Finally observe that in the current case, we are only interested in finding quadratic residues modulo a prime number. More specifically, we want to find –
 if x^{2}≡a (mod p) has a solution for a given a
 Find the value of x if this equation has a solution.
Concluding Remarks:
 The basic reason why I stated this problem as an “easy” problem in the beginning is that it doesn’t require a person to “think a lot”, or think “out of the box” or “discover” some complex logic. All that is needed is a little bit of playing around, some familiarity with Number Theory, and welldeveloped Googlesearch skills. That in fact explains why such problems are actually a feast in programming competitions.
 The ShankTonelli algorithm to solve x^{2} ≡ a (mod P) where P is an odd prime is as follows:
 Express (p1) as a product of an odd number and a power of 2  Let p1 = 2^{n}k
 Let q be a quadratic nonresidue modulo P. (To find q, set initial value of q to 2 and keep on incrementing till you don’t get q^{ }satisfying q^{(p1)/2}≡ 1 (mod p)
 Let t = a^{(k+1)/2 }% p and let r = a^{k}%p
 If r≡1 (mod p) then return t as answer (i.e. algorithm ends).
 Else find v = smallest power of 2 such that r^{v}≡1(mod p). (Let v = 2^{i})
 Let e = 2^{(ni1)}
 Let u = q^{(ke)}%P.
 Set t = (t*u)%P
 Set r = (r*u*u)%P and goto step (4)
To brush up the basics of quadratic equations
A General Tutorial on Quadratic Equations with problems Parabolic Shape of a general Quadratic Curve Note the symmetric shape of a Quadratic curve in contrast to that of a cubic or, quartic polynomial curve. This symmetry can often be exploited.