ĐỊNH LÝ EULER. CHO M LÀ SỐ NGUYÊN DƯƠNG VÀ A LÀ SỐ NGUYÊN TỐ CÙNG N...

3. Định lý Euler. Cho m là số nguyên dương và a là số nguyên tố cùng nhau với m;ϕ(m)là số các số nguyên dương nhỏ hơn m và nguyên tố cùng nhau với m. Khi đó a

^ϕ

(m)

≡1 (mod m). Chú ý: Nếu số nguyên dương m có dạng phân tích thành thừa số nguyên tố: m =





 



1

1

1

−

−

−





 



p .p ...p

^α

^α

^α

thì ϕ(m)=

m 1

1

... 1

1

2

k

CH IN H P H Ụ C K Ỳ T H I H Ọ C S IN H GI Ỏ I C ẤP H AI





 



.

p

p

p

* Ví dụ minh họa:Bài toán 1. Cho ^{a b, ∈Z a b;}

( )

^{, =1} Chứn minh rằng : a

³

−2b

³

không chia hết cho 19.Hướng dẫn giải Ta chứng minh bằng phản chứng như sau: Giả sử

(

^a

³

^−2b

³

)

^{19 khi đó}

( ) ( ) (

^a

³

⁶

^{− 2b}

³

⁶

^{ a}

³

^−2b

³

)

^19.Mặt khác

( ) ( )

^a

³

⁶

^{− 2b}

³

⁶

^=a

¹⁸

^−64b

¹⁸

^{. Nếu a b,} không chia hết cho 19 thì theo định lýFermat (Định lý Fermat: ^a

^p

^≡a

(

^modp

)

^⇒a

^p

⁻

¹

^{≡1 mod}

(

^p

)

Với mọi a nguyên và p nguyên tố).

( ) ( )

⇒ ≡ ≡ ⇒ − ≡ − = − ≡ (Vô lý)

18

18

18

18

1 mod19 64 1 64 63 0 mod19a b a b − ⇒ ⇒a b aNếu một trong hai số chia hết cho 19 thì từ

(

³

²

³

)

^{19 19} ^{vô lý vì}

( )

^{a b, =1.}19bVậy a

³

−2b

³

không chia hết cho 19. Bài toán 2. Chứng minh rằng với mọi số tự nhiên n thì : 2

³

⁴

ⁿ

⁺

¹

+3

²

⁴

ⁿ

⁺

¹

+2007chia hết cho 22 Theo Định lý Fermat bé ta có 2

¹⁰

≡ 1(mod 11) ; 3

¹⁰

≡ 1(mod 11) Ta có 3

⁴

= 81 ≡ 1(mod 10) ⇒ 3

⁴ⁿ⁺¹

= 3. (3

⁴

)

ⁿ

≡ 3(mod 10) ⇒ 3

⁴ⁿ⁺¹

= 10k + 3 , (k ∈ N)Mặt khác 2

⁴

= 16 ≡ 1 (mod 5) ⇒2

⁴ⁿ

≡ 1(mod 5) ⇒ 2

⁴ⁿ⁺¹

= 2.(2

⁴

)

ⁿ

≡ 2 (mod 10) ⇒ 2

⁴ⁿ⁺¹

= 10t + 2 , (t ∈ N)Do đó 2

³

^{4 n 1}

⁺

+3

²

^{4 n 1}

⁺

+2007=2

^{10k 3}

⁺

+3

^{10t 2}

⁺

+2002 5+ ^{=2 . 2}

³

( )

¹⁰

^k

^{+3 . 3}

²

( )

¹⁰

^t

^{+22.91 5+ ≡ 2}

³

^{+ 3}

²

^{+ 0 + 5 ≡} 0 (mod 11) Mà 2

³

^{4 n 1}

⁺

+3

²

^{4 n 1}

⁺

+2007 2 (vì

2

³

^{4 n 1}

⁺

là số chẵn 3

²

^{4 n 1}

⁺

là số lẻ 2007là số lẻ). Do (2 ; 11) = 1 nên 2

³

^{4 n 1}

⁺

+3

²

^{4 n 1}

⁺

+2007  22. Bài toán 3. Cho a a

₁

;

₂

;...;a

₂₀₁₆

là 2016 số nguyên dương . Chứng minh rằng điều kiện cần

CH UY ÊN Đ Ề S Ố H Ọ C

và đủ để a

1

⁵

+a

⁵

2

+ + +a

⁵

3

... a

⁵

2016

30 là a

1

+a

2

+....+a

2016

30.Theo định lý Fermat bé , do 2; 3; 5 là các số nguyên tố và a là số nguyên dương bất kỳ ta có : a

²

≡ a (mod 2)

⇒

a

⁴

= (a

²

)

²

≡ a

²

≡ a (mod 2)

⇒

a

⁵

≡ a (mod 2) a

³

≡ a (mod 3)

^⇒

a

⁵

= a

³

. a

²

≡ a.a

²

≡ a

³

≡ a (mod 3) a

⁵

≡ a (mod 5) Theo tính chất nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư với nhau theo mô đun là BCNN của các môđun ấy. Do đó a

⁵

≡ a (mod 2.3.5) hay a

⁵

≡ a (mod 30)

⇒

a

⁵

– a ≡ 0 (mod 30) Nghĩa là

(

^a

⁵

¹

⁺

^a

⁵

²

⁺

^a

⁵

³

^{+ +}

^{... a}

⁵

²⁰¹⁶

)

^–

⁽

^a

¹

^+a

²

^+....+a

²⁰¹⁶

⁾

^≡0 (mod 30) Vậy a

₁

+a

₂

+....+a

₂₀₁₆

30

⇔

a

₁

⁵

+a

⁵

₂

+a

⁵

₃

+ +... a

⁵

₂₀₁₆

30Bài toán 3. Chứng minh rằng trong các số tự nhiên thế nào cũng có số k sao cho 1983

^k

– 1 chia hết cho 10

⁵

. (Đề thi học sinh giỏi toán cấp 2 toàn quốc năm 1983). Vì 1983 không chia hết cho 2 và không chia hết cho 5 mà 10

⁵

= 2

⁵

.5

⁵

nên (1983; 10

⁵

) = 1. Áp dụng định lý Euler ta có : ( )

¹⁰

⁵

(

⁵

)

1983

^ϕ

≡

1 mod 10

.   Ta có

( )

¹⁰

⁵

^{10 1}

⁵

^{1 1 1 4.10}

⁴

ϕ =  −  − = . Nghĩa là

1983

^4.10

⁴

−

1



10

⁵

2 5Vậy k = 4. 10

⁴

. B. BÀI TẬP ÁP DỤNG