Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 3.2.8 (Primes $p$ such that $\genfrac{(}{)}{}{}{10}{p} = 1$.)

An Introduction to the Theory of Numbers

Exercise 3.2.8 (Primes $p$ such that $\genfrac{(}{)}{}{}{10}{p} = 1$.)

Find all primes p such that ( 10 p ) = 1 .

Answers

Proof. Since 5 ≡ 1 ( mod 4 ) ,

( 5 p ) = 1 ⟺ ( p 5 ) = 1 ⟺ p ≡ 1 , 4 ( mod 5 ) .

Therefore, using ( 10 p ) = ( 2 p ) ( 5 p ) ,

( 10 p ) = 1 ⟺ { ( 2 p ) = 1 and ( 5 p ) = 1 , or ( 2 p ) = − 1 and ( 5 p ) = − 1 , ⟺ { p ≡ 1 , 7 [ 8 ] and p ≡ 1 , 4 [ 8 ] , or p ≡ 3 , 5 [ 8 ] and p ≡ 2 , 3 [ 5 ] , ⟺ { p ≡ 1 [ 8 ] p ≡ 1 [ 5 ]  or  { p ≡ 1 [ 8 ] p ≡ 4 [ 5 ]  or  { p ≡ 7 [ 8 ] p ≡ 1 [ 5 ]  or  { p ≡ 7 [ 8 ] p ≡ 4 [ 5 ]  or  { p ≡ 3 [ 8 ] p ≡ 2 [ 5 ]  or  { p ≡ 3 [ 8 ] p ≡ 3 [ 5 ]  or  { p ≡ 5 [ 8 ] p ≡ 2 [ 5 ]  or  { p ≡ 5 [ 8 ] p ≡ 3 [ 5 ] ⟺ p ≡ 1 , 9 , 31 , 39 , 3 , 27 , 37 , 13 ( mod 40 ) .

So

( 10 p ) = 1 ⟺ p ≡ 1 , 3 , 9 , 13 , 27 , 31 , 37 , 39 ( mod 40 ) .

(The first such primes are p = 3 , 13 , 31 , 37 , 41 , 43 , 53 , 67 , 71 , 79 , 83 , 89 , 107 , 151 , … ) □

Verification with Sage.

sage: prem = prime_range(1000)
sage: l1 = [p for p in prem if kronecker(10,p) == 1]
sage: l2 = [p for p in prem if p % 40 in [1, 3, 9 ,13, 27, 31, 37, 39]]
sage: l1 == l2
True

User profile picture
2024-10-23 09:38
Comments