N G D N G S M L N NH T C A TH A S NGUYÊN T Ấ Ứ Ố Ũ Ớ Ừ Ố Ụ Ủ Ố

TRONG CÁC BÀI TOÁN S H CỐ Ọ

Lê Tr n Nh c Long - THPT Chuyên Lê Quý ô n- à N ng Đ Đ ầ ạ ẵ

----------------------------------------

17/1/2012 T ng di n à n VMF nhân d p sinh nh t 8 n m c a di n à n ễ đ ễ đ ủ ặ ậ ă ị

,s t l ng phân bi ố ẻ ố ự ươ n và hai s nguyên d ố ệ a và b . t t là s m l n nh t c a ố ũ ớ ố ũ ớ ầ ượ nhiên ấ ủ p trong a−b và n. Thì s m l n nh t ấ

Cho p là m t s nguyên t ộ ố G iọ α và β l n l c aủ p trong an−bn là pα+β

ố ũ ớ ệ ấ ủ p trong m là vp(m) ho cặ pα||m (v iớ α là s m l n nh t ấ

Kí hi u s m l n nh t c a ố ũ ớ c aủ p trong m) (Trong bài vi ế t này ta s s d ng kí hi u ẽ ử ụ ệ pα||m)

Ch ng minh: ứ Bài toán a v ch ng minh r ng n u ứ đư ề

Gi ạ ế a≡b(modp) và pβ||n thì pβ||an−bna−b. β

ng h p V i tr ằ sả ử n=pβk. Ta s ch ng minh bài toán quy n p theo n⋮̸p. ớ ườ Khi ó ta có: đ ứ ẽ ợ β=0 t c làứ ak≡bk(modp)

akbn−k−1≡bn−1(modp)⇒∑k=0n−1akbn−k−1≡∑k=0n−1bn−1(modp)≡nbn−1≢0(modp)

Vì an−bna−b=∑k=0n−1an−k−1bk. Do óđ an−bna−b⋮̸p

gi s bài toán úng n ờ ả ử đ đ ẽ ỉ ầ ứ ứ đế β ta s ch ng minh úng ứ đế β+1 t c là ta ch c n ch ng ậ ậ Bây gi n minh p||anp−bnpan−bn. Th t v y:

cđượ

Vì p|a−b nên a=b+xp suy ra ak≡bk+kbk−1xp(modp2) Ta anp−bnpan−bn=∑k=0p−1an(p−k−1)bnk≡∑k=0p−1(bn(p−k−1)+n(p−k−1)xpbn(p−k−1)−1)bnk(mo dp2)

≡pbn(p−1)+∑k=0p−1n(p−k−1)xpbn(p−1)−1≡pbn(p−1)≡p(modp2)

V y ta c ậ đượ p||anp−bnpan−bn. Do óđ

pβ+1||an−bna−b.anp−bnpan−bn=anp−bnpa−b

V y bài toán c ch ng minh ậ đượ ứ

Chú ý:

ng h p ệ t sau ây v i đ

ỏ Ta có m t tr ợ đặ ộ ườ Cho a,b,c∈Z th a mãn ớ p=2 c bi 2α||a2−b22 và 2β||n thì 2α+β||an−bn

c. Ph n ch ng minh k t qu này xin dành cho b n ả ạ đọ ứ ế ầ

V i tr ng h p ng h p c bi ớ ườ ườ ợ đặ ệ t này ch úng khi ỉ đ ợ β=0 thì tr 4|a−b

Và sau ây chúng ta s ẽ đế đ n v i m t s bài toán ng d ng tính ch t này ứ ộ ố ụ ấ ớ

Bài toán 1: Tìm s nguyên d ng ố ấ ỏ ỏ ươ n nh nh t th a mãn 22012|17n−1

L i gi ờ i: ả

Ta có:24||172−12. Gi sả ử 2α||n.

Theo tr ng h p c bi t c a bài toán m u ta ườ ợ đặ ệ ủ ở đầ c đượ

24+α||17n−1. Suy ra α+4≥2012⇒α≥2008.

i u ó có ngh a là Đ ề đ ĩ 22008|n⇒n≥22008 .

Theo b u ta c m ổ đề ở đầ đượ 22012|1722008−1.

V y giá tr nh nh t c a ậ ỏ ị ấ ủ n là 22008

Bài toán 2: i ph Gi ng trình nghi m nguyên ươ ả ệ 23x+1=19.3y

L i gi ờ Áp d ng bài toán m u ta c i: ả ụ ở đầ đượ 3n+1||23n+1 vì 3n là m t s l ộ ố ẻ

c đ ừ đ Vì 19⋮̸3 nên do ó ta đượ 3y||23x+1. T ó suy ra y=x+1

V y ph ng trình tr thành: ậ ươ ở 23x+1=57.3x (*)

ứ tĐặ t=3x. Ta ch ng minh 2t>57t ∀t≥10

Th t v y ta có: ậ ậ 2t=26.2t−6=64.2t−6

đ ớ t=10 Ta có 64>57, ta có 24>10 suy ra 2t−6>t úng v i Gi s úng n ả ử đ đế t ta có 2t−5=2.2t−6>2t>t+1

(*) suy ra ậ đ đ ừ 3x<10⇒x≤2 ng ấ ủ ệ ộ ươ ỉ ấ x=2 th a mãn (*). V y ỏ ậ x=2,y=3 là b nghi m duy nh t c a ph V y b t trên úng nên t Thay x=0;1;2 ch th y trình

Bài toán 3: Cho dãy s c xác nh nh sau ố đượ đị ư

ớ

a1=52 và an+1=a3n−3a2n+6an−3 v i m i

ọ n≥1

Tìm s nguyên d ng n nh nh t sao cho ố ươ ấ ỏ ế ⌊an⌋+1 chia h t cho 32011

ch n i tuy n d thi VMO 2012-KHTNHN vòng 2) ( Đề ọ độ ự ể

L i gi ờ i: ả

tĐặ an=un+1⇒un=an−1

ng th c u bài cho ta : Đẳ ứ đầ

a1−1=32

an+1−1=(an−1)3+3(an−1)

Nên ta suy ra :

u1=32

un+1=u3n+3un

Ta ch ng minh r ng : ứ ằ

u1=23n−1−12n−1∀n≥1 (*)

Th t v y , v i ậ ậ ấ ớ n=1 thì ta th y th a ỏ

N u ng th c trên úng v i ế đẳ đ ứ ứ ớ n=k t c là :

uk=23k−1−12k−1

Khi ó ta có : đ

uk+1=u3k+3uk=23k−13k

Do ó theo quy n p toán h c , ta có (*) . đ ạ ọ

B i th nên : ế ở

32011|⌊an⌋+1=⌊un⌋+2

⇔32011|23n+1,/,/,/,(∗∗)

Theo bài toán 1 ta có 3n+1||23n+1

Nên suy ra n≥2011−1=2010

v y giá tr ậ ấ ầ ỏ ị n nh nh t c n tìm là n=2010

ng, ươ ố l ố ẻ

l n h n 1. Ch ng minh r ng ứ ộ ố ẻ ớ ộ ũ p là m t s nguyên t ộ ố ừ ả ơ Bài toán 4: Cho an+bn=pk v iớ a,b và k là các s nguyên d và n là m t s l ằ n ph i là m t l y th a c a ủ p

nên ta có L i gi ờ ả Vì n l i: ẻ

pk=an+bn=(a+b)(an−1−an−2b+...−abn−2+bn−1)

Vì v yậ a+b=pr v iớ r∈N∗,r≤k

ng nên ta có ố ươ Vì a và b là các s nguyên d r≥1

Gi u ta ử ụ ở đầ c đượ sả ử pβ||n s d ng bài toán m

pβ+r||an−(−b)n=an+bn=pk Suy ra pβ+r||pk⇒+β=k−r

ng ỏ ả đị ố ươ n nh nh t ấ ỏ pβ||n để an+bn=pk,

i u này suy ra Đ ề ng nh nh t th a mãn ấ ươ ỏ ỏ ố n ph i là m t ộ ả pβ||n là pβ.

Vì các số k và r là xác nh nên ph i có s nguyên d th a mãn vì am+bm>an+bn,∀m>n. Nên n ph i là s nguyên d ả ủ p. l y th a c a ừ ũ

Bài toán c ch ng minh đượ ứ

Bài toán 5:Tìm t ng ấ ả t c các s nguyên d ố ỏ ươ n th a mãn n2|2n+1

(IMO1990) L i gi i: ả ờ

Gi ng sao cho ươ sả ử n là s nguyên d ố n2|2n+1 (1)

, d th y ỏ Suy ra n ph i là m t s l ả ộ ố ẻ ễ ấ n=1 th a mãn

c nguyên t nh nh t c a ướ ố ỏ ấ ủ n. Xét n>1, g iọ p1 là

Ta có : 22n≡1(modp1)

G iọ d=ordp12 thì d

N uế d=1 thì p1=1 vô lí. V yậ d=2 và p1|3 suy ra p1=3.

Gi u ta c ở đầ sả ử pβ||3 thì theo bài toán m đượ 3β+1||2n+1

K t h p v i (1) ta ế ợ ớ c đượ

32β|3β+1||2n+1⇒2β≤β+1⇒β≤1 3||n⇒n=3k;(n;k)=1 T ó suy ra ừ đ

c nguyên t nh nh t c a ướ ố ỏ G iọ p2 là ấ ủ k. Ta có 26k≡1(modp2)

G iọ d2=ordp22⇒d2

D th y ể ằ ặ ễ ấ d2 không th b ng 1 ho c 2

N uế d2=3, ta có p2|7⇒p2=7

N uế d2=6, ta có p2|63=7.9⇒p2|7⇒p2=7

Mà ta có: 23≡1(mod7)⇒2k+3≡2k(mod7)

và 2≡2(mod7) và 22≡4(mod7)

Nên ph ng trình ươ ệ 2k −≡ 1(mod7) không có nghi m nguyên

i. V y c nguyên ế ớ ộ ướ ọ k và p2 không t n t ồ ạ ậ nch có m t ỉ

duy nh t là 3, l ấ ạ Suy ra 27k+1 không chia h t cho 7 v i m i 3||n nên suy ra n=3 i có t ố

V y các giá tr c a ậ ị ủ n c n tìm là ầ n=1 và n=3.