Therefore we assume p is an odd prime in this section. We only consider odd primes here because the case p = 2 was handled above. So if a has any square root modulo p n - call it x - then it has exactly two roots: x and – x. Therefore, either x ≡ y (mod p n) or x ≡ – y (mod p n). Since p n divides ( x+ y)( x– y), it only divides one of ( x+ y) and ( x– y). It follows that p either divides ( x+ y) or ( x– y) but not both. If p divided x, then p would divide x 2, and therefore p would divide a, and a would not be relatively prime to p n. Now x 2 ≡ a (mod p n), and so x 2 = k p n + a for some k. Since p is an odd prime, p does not divide 2 and so p would divide both x and y. If p divided both x+ y and x– y, then p would divide both their sum and their difference, 2 x and -2 y. Thus p n divides the product ( x+ y)( x– y) and so p divides the product as well. Then x 2 – y 2 ≡ ( x – y)( x + y) ≡ 0 (mod p n). Suppose x 2 = y 2 ≡ a (mod p n) where p is an odd prime and a is relatively prime to p. (Thanks to Nemo for providing this proof.) Next we’ll show that if we find a solution x, there is exactly one other solution, – x.
#1 mod 2 how to
The procedure above shows how to construct one solution to x 2 ≡ a (mod p n) but it does not tell us whether there are more solutions. Then x k+1 = x k – ( x k 2 – a) y k is a solution to x 2 ≡ a (mod p k+1). Let y k be a solution to 2 x k y k ≡ 1 (mod p k). Suppose x k is a solution to x 2 ≡ a (mod p k) for some k ≥ 1. Then there is a procedure based on Hensel’s Lemma that can take a solution to x 2 ≡ a (mod p) and produce solutions to x 2 ≡ a (mod p n) for n = 2, 3, 4, etc. Let p be an odd prime and let a be any integer relatively prime to p. Then x k+1 defined by x k + i 2 k-1 is a solution to x k+1 2 ≡ a (mod 2 k+1). By definition, this means x 2 – a is divisible by 2 k. The solutions to x 2 ≡ a (mod 2 n) for n > 3 can be found by the procedure below that starts with each of the solutions (mod 8) and produces solutions by induction for higher powers of 2.
If a ≡ 1 (mod 8) then x 2 ≡ a (mod 8) has four solutions: 1, 3, 5, and 7. Next, x 2 ≡ a (mod 4) has a solution if and only if a ≡ 1 (mod 4), in which case the solutions are x ≡ 1 (mod 4) and x ≡ 3 (mod 4).įinally, for n ≥ 3, x 2 ≡ a (mod 2 n) has four unique solutions if a ≡ 1 (mod 8) and no solutions otherwise. (Since we are assuming m and a are relatively prime, if m has a power of 2 as a factor, a must be odd.)įirst, x 2 ≡ a (mod 2) has a solution, namely x ≡ 1 (mod 2). (To see this, note that if x 2 – a is divisible by p n then it is certainly divisible by p.) Perhaps surprisingly, this is also a sufficient condition.
Also, powers of 2 must be handled separately from powers of odd primes, and the former is sometimes neglected.įor any prime p, a necessary condition for x 2 ≡ a (mod p n) to have a solution is for x 2 ≡ a (mod p) to have a solution. This is the part that is often not presented clearly.
Reduce prime power moduli to prime moduli Conversely, if you find solutions to each of the prime power congruences, you can use the Chinese Remainder Theorem to produce a solution to the original problem. If the congruence x 2 ≡ a (mod m) has a solution, that solution is necessarily a solution to each of the prime power congruences x 2 ≡ a (mod p i e i). Factor the modulus m into prime powers: m = p 1 e 1 p 2 e 2 … p r e r. The first step in the reduction is clear. Reduce general moduli to prime power moduli Throughout these notes we will assume m and a have no factors in common. However, I haven’t seen a book that is entirely clear on exactly how to reduce the general problem to the problem of prime moduli, or how you can unwind the reduction to produce a solution to the original problem.
#1 mod 2 android
Except explicit open source licence (indicated CC / Creative Commons / free), the "Modulo N Calculator" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or the "Modulo N Calculator" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, copy-paste, or API access for "Modulo N Calculator" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.How do you solve congruences of the form x 2 ≡ a (mod m)? Said another way, how do you find square roots in modular arithmetic?Įvery number theory book I’ve seen points out that the general problem of solving x 2 ≡ a (mod m) can be reduced to the solving the special case where m is a prime then spends most of the time studying this special case in detail. Ask a new question Source codeĭCode retains ownership of the online "Modulo N Calculator" source code. In most computation languages, the modulo operator % has the same precedence as the multiplication or division operations.
0 kommentar(er)
