Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 3.1.8 (Solve $x^2 \equiv -1$ modulo $61,59,365,3599,122,244$)

An Introduction to the Theory of Numbers

Exercise 3.1.8 (Solve $x^2 \equiv -1$ modulo $61,59,365,3599,122,244$)

How many solutions are there to each of the congruences

( a ) x 2 ≡ − 1 ( mod 61 ) ( b ) x 2 ≡ − 1 ( mod 59 ) ( c ) x 2 ≡ − 1 ( mod 365 ) ( d ) x 2 ≡ − 1 ( mod 3599 ) ( e ) x 2 ≡ − 1 ( mod 122 ) ( f ) x 2 ≡ − 1 ( mod 244 )

Answers

Proof. Here 59 and 61 are prime numbers.

(a)
Since ( − 1 61 ) = 1 , the congruence x 2 ≡ − 1 ( mod 61 ) has 2 solutions ( 11 and 50 modulo 61 ).
(b)
Here ( − 1 59 ) = − 1 , therefore the congruence x 2 ≡ − 1 ( mod 59 ) has no solution.
(c)
Using 365 = 5 ⋅ 73 , where 5 and 73 are distinct primes, the congruence x 2 ≡ − 1 ( mod 365 ) is equivalent to { x 2 ≡ − 1 ( mod 5 ) , x 2 ≡ − 1 ( mod 73 ) , (1)

Since ( − 1 5 ) = 1 and ( − 1 73 ) = 1 , this system has 4 solutions modulo 365 .

(With some more work, these solutions are 27 , 173 , 192 , 338 modulo 365 .)

(d)
Using 3599 = 59 ⋅ 61 , the congruence x 2 ≡ − 1 ( mod 3599 ) is equivalent to { x 2 ≡ − 1 ( mod 59 ) , x 2 ≡ − 1 ( mod 61 ) , (2)

By part (b), the first congruence has no solution, therefore the congruence x 2 ≡ − 1 ( mod 3599 ) has no solution.

(e)
The congruence x 2 ≡ − 1 ( mod 122 ) is equivalent to { x 2 ≡ − 1 ( mod 2 ) , x 2 ≡ − 1 ( mod 61 ) ,

that is

{ x ≡ 1 ( mod 2 ) , x ≡ 11 ( mod 61 ) ,  or  { x ≡ 1 ( mod 2 ) , x ≡ 50 ( mod 61 ) .

By the Chinese Remainder Theorem, the congruence x 2 ≡ − 1 ( mod 122 ) has two solutions modulo 122 (explicitely x ≡ ± 11 ( mod 122 ) )

(f)
Since the congruence x 2 ≡ − 1 ( mod 4 ) has no solution, a fortiori the congruence x 2 ≡ − 1 ( mod 244 ) has no solution.
□
User profile picture
2024-10-17 10:22
Comments