Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 3.6.4 (Find integers $x$ and $y$ such that $x^2 + y^2 = 89753$)

An Introduction to the Theory of Numbers

Exercise 3.6.4 (Find integers $x$ and $y$ such that $x^2 + y^2 = 89753$)

Use the method of Example 3 to find integers x and y such that x 2 + y 2 = 89753 , given that this number is prime.

Answers

Proof. Put p = 89753 . Since p ≡ 1 ( mod 4 ) ,

( 3 p ) = ( p 3 ) = ( 2 3 ) = − 1 ,

so 3 is a nonresidue modulo p .

Let s be the unique integer such that 0 < s < p and s ≡ 3 ( p − 1 ) ∕ 4 ( mod p ) . By fast exponentiation, we obtain

s = 18750 .

(With Sage,

sage: p = 89753
sage: is_prime(p)
True
sage: kronecker(2,p)
1
sage: kronecker(3,p)
-1
sage: Mod(3,p)^((p-1)//4)
18750 )

Then

s 2 ≡ 3 ( p − 1 ) ∕ 2 ≡ ( 3 p ) = − 1 ( mod p ) .

So s 2 = kp − 1 , where k = 3917 , so that 4 s 2 − 4 kp = − 4 , which means that the form

f ( x , y ) = p x 2 + 2 sxy + k y 2 = 89753 x 2 + 37500 xy + 3917 y 2

has discriminant − 4 , so is properly equivalent to f 0 ( x , y ) = x 2 + y 2 . There is a matrix G ∈ Γ such that f ⋅ G = f 0 . I keep track of G in the algorithm to reduce f , so that f ⋅ G is the form in the same line.

We obtain

a b c Operation G
89753 37500 3917 S I
3917 - 37500 89753 T 5 ( 0 1 − 1 0 )
3917 1670 178 S ( 0 1 − 1 − 5 )
178 -1670 3917 T 5 ( − 1 0 5 − 1 )
178 110 17 S ( − 1 − 5 5 24 )
17 -110 178 T 3 ( 5 − 1 − 24 5 )
17 -8 1 S ( 5 14 − 24 − 67 )
1 8 17 T − 4 ( − 14 5 67 − 24 )
1 0 1 ( − 14 61 67 − 292 )

The last line means that

f ⋅ G = f 0 ,  where  G = ( α β γ δ ) = ( − 14 61 67 − 292 ) ,

(and G = S T 5 S T 5 S T 3 S T − 4 ). Thus

f = f 0 ⋅ G − 1 ,  where  G − 1 = ( δ − β − γ α ) .

Therefore

f ( x , y ) = p x 2 + 2 sxy + k y 2 = f 0 ( δx − βy , − γx + αy ) = ( δx − βy ) 2 + ( − γx + αy ) 2 ,

thus

f ( 1 , 0 ) = p = γ 2 + δ 2 ,

so

p = 89753 = 6 7 2 + 29 2 2 .

□

We can code the reduction in Sage with

  def is_reduced(a,b,c):
    """ is q = (a, b, c) reduced ? (D < 0)
    """
    if not(abs(b) <= a and a <= c):
        return False
    if abs(b) == a or a == c:
        return b >= 0
    return True

def reduce(q, verbose = 0):
    a, b, c = q
    G = Matrix([[1,0],[0,1]])
    liste = []
    while not is_reduced(a, b, c):
        if c < a:
            (a, b, c) = (c, -b, a)
            A = Matrix([[0, 1],[-1, 0]])
        elif abs(b) > a or -b == a:
            k = (a - b) // (2 * a)
            c = a * k * k + b * k + c
            b = b + 2 * k * a
            A = Matrix([[1, k ],[0, 1]])
        G = G * A
        liste.append(A)
        if verbose:
            print(’A   = ’); print(A)
            print(’G   = ’); print(G)
            print(’f.G = ’); print(a,b,c)
    return (a, b, c), G, liste

f = (89753, 37500, 3917)

(a,b,c), G, liste = reduce(f)

(a,b,c)
      (1,0,1)

 G 

( − 14 61 67 − 292 ) 

liste

[ ( 0 1 − 1 0 ) , ( 1 5 0 1 ) , ( 0 1 − 1 0 ) , ( 1 5 0 1 ) , ( 0 1 − 1 0 ) , ( 1 3 0 1 ) , ( 0 1 − 1 0 ) , ( 1 − 4 0 1 ) ]

To obtain details:

reduce(f, verbose = 1)

(This gives the preceding array)

We can write these procedures in pure Python if we write a python class of matrices 2 × 2 with the usual operations. It is easy to add a procedure that compute ( a , b ) such that p = a 2 + b 2 .

Try with the primes

1234567891234567891234567909 , 1 0 50 + 577 , 1 0 100 + 949 .

User profile picture
2024-11-27 16:09
Comments