mer02.pdf

(240 KB) Pobierz
Podró»epoImperiumLiczb
Cz¦±¢08. LiczbyMersenne’a,FermataiInne
Liczby
Rozdział2
2.Liczbypostaci a n − b n
AndrzejNowicki20maja2012, http://www.mat.uni.torun.pl/~anow
Spistre±ci
2Liczbypostacia n -b n
19
Ogólne własno±ci liczb a n - b n . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
19
Liczby postaci a n - 1
2.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Liczby 3 n - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3
24
Liczby 5 n - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4
26
Liczby 6 n - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5
27
Liczby 7 n - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6
28
Liczby 11 n - 1
2.7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Inne liczby postaci a n - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8
31
Liczby postaci (a+1) n - a n . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9
31
Liczby a n - a m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10
33
2.11
Liczby pseudopierwsze i liczby Carmichaela . . . . . . . . . . . . . . . . . . .
35
Wszystkie ksi¡»ki z serii ”Podró»e po Imperium Liczb” napisano w edytorze L A T E X.
Spisy tre±ci tych ksi¡»ek oraz pewne wybrane rozdziały mo»a znale¹¢ na internetowej stronie
autora: http://www-users.mat.uni.torun.pl/~anow .
1244564223.005.png 1244564223.006.png
2Liczbypostacia n -b n
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
2.1Ogólnewłasno±ciliczba n -b n
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
2.1.1. Niecha>bb¦d¡ liczbami naturalnymi i niech
v n = a n − b n
dlan 2 N 0 . Je±lin<m, tov n <v m .
D. v m − v n = a m − b m − a n + b n = a n ( a m − n − 1) − b n ( b m − n − 1)
>a n ( b m − n − 1) − b n ( b m − n − 1)
= v n ( b m − n − 1) > 0 .
2.1.2. Niecha>bb¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi. Niechm,n 2 N . Je±lir
jest reszt¡ z dzieleniamprzezn, to
a m − b m ,a n − b n
a n − b n ,a r − b r
=
.
D. Niech m = kn + r , gdzie k i 0 6 r<n s¡ liczbami całkowitymi. Mamy wtedy równo±¢
a m − b m = ( a m − n b 0 + a m − 2 n b n + ··· + a r b m − n − r )( a n − b n ) + b kn ( a r − b r )
i z tej równo±ci wynika, »e ( a m − b m ,a n − b n ) = a n − b n ,b kn ( a r − b r ) . Poniewa» ( a,b ) = 1, wi¦c
a n − b n ,b kn = 1 i st¡d
a n − b n ,b kn ( a r − b r ) = ( a n − b n ,a r − b r ) .
Zatem, ( a m − b m ,a n − b n ) = ( a n − b n ,a r − b r ).
2.1.3. Niecha>bb¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi. Wtedy
( a n − b n ,a m − b m )= a ( n,m ) − b ( n,m )
dla wszystkichn,m 2 N . ([MM]54(2)(1981)86,[G-kp]174(38),[Sand]230) .
D. Dowodzimy to dokładnie tak samo jak twierdzenie 1.3.2. Wykorzystujemy algorytm Euklidesa
i powy»szy fakt 2.1.2. Oznaczmy: v s = a s − b s dla s > 0.
Je»eli m = n to ( m,n ) = m i ( v m ,v n ) = v m = v ( m,n ) . Załó»my, »e m>n i obliczmy najwi¦kszy
wspólny dzielnik ( m,n ) przy pomocy algorytmu Euklidesa. Otrzymujemy wtedy ci¡g równo±ci:
m = k 1 n + r 1 ,n = k 2 r 1 + r 2 ,r 1 = k 3 r 2 + r 3 ,...,r i − 1 = k i +1 r i + r i +1 ,r i = k i +2 r i +1 + r i +2 ,
w których wszystkie k j ,r j s¡ nieujemnymi liczbami całkowitymi oraz
m>n>r 1 >r 2 > ··· >r i +1 >r i +2 = 0 .
Mamy wtedy ( m,n ) = r i +1 . Z faktu 2.1.2 otrzymujemy ci¡g równo±ci
( v m ,v n ) = ( v n ,v r 1 ) = ( v r 1 ,v r 2 ) = ( v r 2 ,v r 3 ) = ··· = v r i +1 ,v r i +2
= v r i +1 ,v 0 = v r i +1 , 0 = v r i +1 = v ( m,n ) .
Zatem ( v m ,v n ) = v ( n,m ) .
19
1244564223.007.png 1244564223.008.png 1244564223.001.png 1244564223.002.png
 
20 AndrzejNowicki,LiczbyMersenne’aiinne. 2.Liczbypostacia n -b n
Z powy»szego twierdzenia wynikaj¡ nast¦puj¡ce wnioski.
2.1.4. Niechm,n 2 N . Je±lia>bs¡ wzgl¦dnie pierwszymi liczbami naturalnymi, to liczba
a m − b m dzieli liczb¦a n − b n wtedy i tylko wtedy, gdyndzielim.
D. Niech v s = a s − b s , dla s 2 N 0 . Je±li m | n , to ( m,n ) = m i wtedy v m = v ( m,n ) = ( v m ,v n ),
czyli v m | v n . Załó»my, »e v m | v n . Wtedy v m = ( v m ,v n ) = v ( m,n ) , wi¦c m = ( m,n ) (patrz 2.1.1) i
st¡d m | n .
2.1.5. Niechm,n 2 N . Je±lia>bs¡ wzgl¦dnie pierwszymi liczbami naturalnymi, to
a n − b n ,a m − b m
= a − b () ( n,m ) = 1 .
D. Niech v s = a s − b s , dla s 2 N 0 . Je±li ( m,n ) = 1, to ( v n ,v m ) = v ( m,n ) = v 1 = a − b . Załó»my,
»e ( v n ,v m ) = a − b = v 1 . Wtedy v ( n,m ) = ( v n ,v m ) = v 1 i z 2.1.1 wynika, »e ( n,m ) = 1.
W poni»szych stwierdzeniach a i b s¡ liczbami całkowitymi oraz n i m s¡ liczbami natu-
ralnymi.
2.1.6. n | a − b = ) n 2 | a n − b n
2.1.7. Je±li ( a, 133) = ( b, 133) = 1 , to 133 | a 18 − b 18 . ([Grif]89) .
2.1.8. Je±lia,bs¡ ró»nymi liczbami zespolonymi takimi, »e liczby
a 2 − b 2 , a 3 − b 3 , a 5 − b 5
s¡ wymierne, toa,b,cs¡ liczbami wymiernymi. ([MM]73(4)(2000)328) .
Ka»da z liczb postaci a n − b n (gdzie a>b s¡ liczbami naturalnymi) jest podzielna przez
( a − b ). Mamy zatem liczby naturalne postaci
a n − b n
a − b = a n − 1 + a n − 2 b 1 + a n − 3 b 2 + ··· + a 1 b n − 2 + b n − 1 .
2.1.9. Niecha>bb¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi. Oznaczmy:
w n = a n − b n
a − b , dlan 2 N .
Niechn,m 2 N . Wtedy:
(1) ( w n ,w m ) = w ( n,m ) ;
(2) ( w n ,w m ) = 1 () ( n,m ) = 1 ;
(3) w n | w m () n | m.
D. (1). Niech v s = a s − b s dla s 2 N. Wtedy v s = ( a − b ) w s i mamy:
( a − b )( w n ,w m ) = (( a − b ) w n , ( a − b ) w m ) = ( v n ,v m ) = v ( n,m ) = ( a − b ) w ( n,m ) .
Zatem ( w n ,w m ) = w ( n,m ) . Wykorzystali±my fakt 2.1.3. Własno±ci (2) i (3) wykazujemy tak samo jak
to zrobili±my w 2.1.5 i 2.1.4.
1244564223.003.png
 
AndrzejNowicki,LiczbyMersenne’aiinne. 2.Liczbypostacia n -b n
21
2.1.10. Niecha>bb¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi i niech
w n = a n − b n
a − b
dlan 2 N . Je±liw n jest liczb¡ pierwsz¡, tonjest liczb¡ pierwsz¡.
D. Je±li n > 2 nie jest liczb¡ pierwsz¡, to istnieje liczba naturalna d taka, »e d | n , 1 <d<n i
wtedy w d | w n oraz 1 <w d <w n .
2.1.11. Je±lin | a n − b n i a 6 = b, to liczba całkowita a n − b n
a − b jest podzielna przezn.
([GaT]33/68) .
a m − b m
a − b ,a − b
a − b,mb m − 1
2.1.12.
=
. ([MM]54(1)(1981)37,[Gibl]18) .
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
2.2Liczbypostacia n -1
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
2.2.1. Konsekwencje twierdzenia Eulera lub jego uogólnienia.
24 | a 2 − 1 dlaa 2 Z , ( a, 6) = 1 .
(1)
240 | a 4 − 1 dlaa 2 Z , ( a, 60) = 1 .
(2)
16 | a 4 − 1 dla nieparzystycha 2 Z .
(3)
32 | a 5 − 1 dla nieparzystycha 2 Z .
(4)
2.2.2. ( a, 35) = 1 = ) 240 | ( a 4 − 1)( a 4 + 15 a 2 + 1) . ([DoC]179) .
2.2.3. 1976 | (2 n + 1) 36 − 1 . ([Kw]12/197654) .
a n − 1 ,a m − 1
= a ( n,m ) − 1 , dlam,n,a 2 N ,a> 1 . ([S59]11,[Mol2]27,[K-Me]z.125) .
2.2.4.
D. Jest to szczególny przypadek faktu 2.1.3. Przedstawiamy inny dowód.
Istniej¡ liczby naturalne x i y takie, »e ( m,n ) = mx − ny . Niech d = ( a m − 1 ,a n − 1). Wtedy
a ( m,n ) − 1 | a m − 1 oraz a ( m,n ) − 1 | a n − 1, sk¡d a ( m,n ) − 1 | d .
Z drugiej strony d | a m − 1, sk¡d d | a mx − 1 oraz d | a n − 1, czyli d | a ny − 1. Zatem,
d | a mx − a ny = a ny ( a mx − ny − 1) ,
a poniewa» z tego, »e d | a m − 1 i a> 1 wynika, »e ( d,a ) = 1, wi¦c d | a mx − ny − 1, czyli d | a ( m,n ) − 1.
Ostatecznie d = a ( m,n ) − 1.
a m − 1
a − 1 ,a − 1
2.2.5.
= ( a − 1 ,m ) , dlaa,m 2 N ,a > 2 . ([Mat]4/1960241,[S64]8) .
D. Jest to szczególny przypadek faktu 2.1.12.
1244564223.004.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin