Associated Topics || Dr. Math Home || Search Dr. Math

### Using Modular Arithmetic to Find All Solutions to the Diophantine Equation Ny + 1 = x^2

```Date: 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.

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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search