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.

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/