Exercise 9.1.5

Verify the formula for Φ 105 ( x ) given in Example 9.1.7.

Answers

Proof. The factors of 105 = 3 × 5 × 7 are 105 , 35 , 21 , 15 , 7 , 5 , 3 , 1 , thus

x 105 − 1 = Φ 105 Φ 35 Φ 21 Φ 15 Φ 7 Φ 5 Φ 3 Φ 1 .

As x 35 − 1 = Φ 35 Φ 7 Φ 5 Φ 1 , we obtain

x 105 − 1 = ( x 35 − 1 ) Φ 105 Φ 21 Φ 15 Φ 3 ,

that is

x 70 + x 35 + 1 = Φ 105 Φ 21 Φ 15 Φ 3 .

Moreover x 21 − 1 = Φ 21 Φ 7 Φ 3 Φ 1 , so

Φ 21 = ( x 21 − 1 ) x − 1 x 7 − 1 x − 1 x 3 − 1 1 x − 1 = x 21 − 1 ( x 7 − 1 ) ( x 2 + x + 1 ) = x 14 + x 7 + 1 x 2 + x + 1 = x 12 − x 11 + x 9 − x 8 + x 6 − x 4 + x 3 − x + 1 .

Similarly x 15 − 1 = Φ 15 Φ 5 Φ 3 Φ 1 , so

Φ 15 = x 15 − 1 ( x 5 − 1 ) ( x 2 + x + 1 ) = x 10 + x 5 + 1 x 2 + x + 1 = x 8 − x 7 + x 5 − x 4 + x 3 − x + 1 .

Therefore

Φ 105 = x 70 + x 35 + 1 Φ 21 Φ 15 Φ 3 = x 70 + x 35 + 1 x 22 − x 21 + x 19 − x 18 + x 17 + x 12 − x 11 + x 10 + x 5 − x 4 + x 3 − x + 1 = x 48 + x 47 + x 46 − x 43 − x 42 − 2 x 41 − x 40 − x 39 + x 36 + x 35 + x 34 + x 33 + x 32 + x 31 − x 28 − x 26 − x 24 − x 22 − x 20 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 − x 9 − x 8 − 2 x 7 − x 6 − x 5 + x 2 + x + 1 □
User profile picture
2022-07-19 00:00
Comments