Using Modular Arithmetic to Find All Solutions to the Diophantine Equation Ny + 1 = x^2Date: 12/13/2008 at 04:10:52 From: Sun Subject: Diophantine equation Ny + 1 = x^2 Without resorting to an exhaustive attack, I want to find all the solutions to the Diophantine equation Ny + 1 = x^2, where N is the data, X and Y are unknown numbers. The use of exhaustive attack method to find all the answers is a waste of time and energy. Would like to find a very quick way! Date: 12/14/2008 at 18:05:42 From: Doctor Vogler Subject: Re: Diophantine equation Ny+1=x^2 Hi Sun, Thanks for writing to Dr. Math. This is a problem of modular arithmetic. Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html You are asking to solve the modular equation x^2 = 1 (mod N) which is the same as finding the square roots of 1 mod N. To do this, you need first to factor the number N into prime factors. Mod each odd prime power, there are exactly two square roots of 1, namely 1 and -1. An even prime power is a power of 2. Mod 2, there is one square root of 1, namely 1 (which is the same, mod 2, as -1). Mod 4, there are two square roots of 1, namely 1 and -1. And mod 2^k, for k > 1, there are four square roots of 1, namely 1, -1, 2^(k - 1) + 1, and 2^(k - 1) - 1. (Alternately, you can think of these as two square roots mod 2^(k - 1).) You get to pick one of the square roots mod each prime power of N, and then you can put them together using the Chinese Remainder Theorem to get a square root of 1 mod N. That is, for each way to choose square roots of 1 mod prime power factors of N, there will be one square root of N. I'll elaborate with an example. Take N = 360 = 2^3 * 3^2 * 5. There are four square roots mod 2^3, namely 1, 3, 5, and 7. (Note: -1 = 7 mod 2^3.) There are two square roots mod 3^2, namely 1 and 8. (Note: -1 = 8 mod 3^2.) And there are two square roots mod 5, namely 1 and 4. (Note: -1 = 4 mod 5.) Therefore, there are 4*2*2 = 16 square roots mod 360. They come from the triples 1 mod 8, 1 mod 9, 1 mod 5 => 1 mod 360 1 mod 8, 1 mod 9, 4 mod 5 => 289 mod 360 1 mod 8, 8 mod 9, 1 mod 5 => 161 mod 360 1 mod 8, 8 mod 9, 4 mod 5 => 89 mod 360 3 mod 8, 1 mod 9, 1 mod 5 => 91 mod 360 3 mod 8, 1 mod 9, 4 mod 5 => 19 mod 360 3 mod 8, 8 mod 9, 1 mod 5 => 251 mod 360 3 mod 8, 8 mod 9, 4 mod 5 => 179 mod 360 5 mod 8, 1 mod 9, 1 mod 5 => 181 mod 360 5 mod 8, 1 mod 9, 4 mod 5 => 109 mod 360 5 mod 8, 8 mod 9, 1 mod 5 => 341 mod 360 5 mod 8, 8 mod 9, 4 mod 5 => 269 mod 360 7 mod 8, 1 mod 9, 1 mod 5 => 271 mod 360 7 mod 8, 1 mod 9, 4 mod 5 => 199 mod 360 7 mod 8, 8 mod 9, 1 mod 5 => 71 mod 360 7 mod 8, 8 mod 9, 4 mod 5 => 359 mod 360 To understand how to make the conversion I made on each line above, please look up the Chinese Remainder Theorem. Now, for each of these solutions z mod N, there are a family of integer solutions to your equation, which come from x = z + mN. For example, in the third line above, we have x = 161 mod 360, which means that x = 161 + 360m for some integer m, and therefore y = (x^2 - 1)/N = ((161 + 360m)^2 - 1)/360 = (129600m^2 + 115920m + 25921 - 1)/360 = 360m^2 + 322m + 72. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/