Zahlentheorie fuer Einsteiger 3834804401, 978-3-8348-0440-2 [PDF]
139 74 10MB
German Pages 215
![Zahlentheorie fuer Einsteiger
3834804401, 978-3-8348-0440-2 [PDF]](https://vdoc.tips/img/200x200/zahlentheorie-fuer-einsteiger-3834804401-978-3-8348-0440-2.jpg)
- Author / Uploaded
- Andreas Bartholomé
Datei wird geladen, bitte warten...
Zitiervorschau
Andreas Bartholomé | Josef Rung | Hans Kern Zahlentheorie für Einsteiger
Aus dem Programm
Mathematik für Einsteiger
Algebra für Einsteiger von Jörg Bewersdorff Algorithmik für Einsteiger von Armin P. Barth Diskrete Mathematik für Einsteiger von Albrecht Beutelspacher und Marc-Alexander Zschiegner Finanzmathematik für Einsteiger von Moritz Adelmeyer und Elke Warmuth Graphen für Einsteiger von Manfred Nitzsche Knotentheorie für Einsteiger von Charles Livingston Stochastik für Einsteiger von Norbert Henze Strategische Spiele für Einsteiger von Alexander Mehlmann Zahlen für Einsteiger von Jürg Kramer Zahlentheorie für Einsteiger von Andreas Bartholomé, Josef Rung und Hans Kern
www.viewegteubner.de
Andreas Bartholomé | Josef Rung | Hans Kern
Zahlentheorie für Einsteiger Eine Einführung für Schüler, Lehrer, Studierende und andere Interessierte Mit einem Geleitwort von Jürgen Neukirch 6., überarbeitete und erweiterte Auflage STUDIUM
Bibliografische Information Der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über abrufbar.
Dr. Andreas Bartholomé und Josef Rung unterrichten am Hans-Leinberger-Gymnasium in Landshut. Anschrift: Jürgen-Schumann-Straße 20, 84034 Landshut Dr. Hans Kern unterrichtet am Schyren-Gymnasium in Pfaffenhofen/Ilm. Anschrift: Niederscheyerer Straße 4, 85276 Pfaffenhofen Online-Service: http://www.andreasbartholome.de
1. Auflage 1995 2., überarbeitete Auflage 1996 3., verbesserte Auflage 2001 4., durchgesehene Auflage 2003 5., verbesserte Auflage 2006 6., überarbeitete und erweiterte Auflage 2008 Alle Rechte vorbehalten © Vieweg+Teubner Verlag |GWV Fachverlage GmbH, Wiesbaden 2008 Lektorat: Ulrike Schmickler-Hirzebruch | Susanne Jahnel Der Vieweg+Teubner Verlag ist ein Unternehmen von Springer Science+Business Media. www.viewegteubner.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: MercedesDruck, Berlin Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-0440-2
! "
"# ! $ " % & # ' (
) ( '
% ) % * ( ' % (
' +
, * ' - % . " . / "0 ' "
1*
' + ( % 2' - / /
/ + ' 1 ( # % 2 ( 3 / ' 4 1 $$ -
5 - # 6 2' + + %$
7 / 5 ' + (
- *' - $#
6 8
'
+ ( *
9
"0 ' 9 :# ; % *
" ' >?
5 ' +' @ 4
ÎÓÖÛÓÖØ
! "
# ! ! $ % " !
! & !
% # ! '
" ! & (
!
! ) ( & (
$ * + ( & ( ! % &( % (
! , ! - (
(
(
% .
! ( -( / 0
1 -
! 2 +% 3 4
! " # $ % & # # 1, 2, 3 $ ! & $ '! (
! $ ) *$ (!! $ +! , $ , ( -$ $ % ($! ) . / 0110213 13214 -, !,56 7 $ ! 8 "! ! 9 % : ;: < # ! -
(! (! = .
%
! " # $ % $ & ' ( ) * % % + ,, * % * % - . / ' % & % 0 - 12 3 # . 4 1 /% 5 3 0 % & % 6 ! " * . . 7 % 0 & 3 13 ( . 8 ! 7 1 9 : 9 "1 ;?@ - 0 9 A & B % % 8 !6 3 - " : :0 ' 0 : 300
' C 7 6
D % 0 * & , - 4 / * , ' , : . % * : 4 90 % A =E ' ( ! 6A " ( 200 A 3
4 % ! " - &, : A ' , Q R
< ! " # ! # ! $ Z/pZ p # %
& ' ( ' ! ! ) Z[φ] φ * !
+ , x2 − x − 1 = 0 - ' , * ! ! ' + Z . * / + / Z[φ] ) ! *" (
! * ! " 0 )/ 1 . 2 ! # - ! ' 3 / * 3 2
% / % / + ( !! 4 ! / !
0 ( ! #! ) ' ! / ! / ( ( / ! ( #! + ' ' ! ( . ( ! . 5 6
/ 6 * #! ! ,3$ + $ 7! 8 + 0 #! ! 6 8 3! ( & 0 / 9 9 1 ! 2 : + . ( ! + , ;< ! !1 ( , / ( ( ' ! / 1 ! ! ! +
(
!
" #$$%& '
! # $ % '() !*+ , ' ! " ' " - + " ! '+ 0 + 1 2 3 *+ + 1 # + 1 ! *+ *+ ! 45
"
/ 1
& .
" / 1 & .
, 5 6 + + $ 7 *+ ! # ' 8 9 5 :*+3 , 5 ; + p + 5 !
" & " " " ". // 1" & & . ."
& . / 1 " " "1 /
a # $ $ ! ' ( )! *'+,! -
! "
%& % %% .
! " #$
%&! '()*+, - ).
! " # $ % & ' $ $ % () * s
s
s
s
s
+ , - .
s
- ∞
/ % 0 '
1
2 1
3 4 5 1
4 6 1 4 ' 1 7 4 7 & 1 8 0 / N = {0, 1, 2, 3, 4 . . .} 5 94 ' " : / 1 2 ;
7 74 1 ' : 4 0 $ 6 2 1 74' 2 ; 1
!" # ! !$ % ! &'" ( &% % N
)! ! * + , - % $. $ ! % + /! 0 1 ! $
1 $, ! " #
$
D
C
y F x A
x
B
2 3 3, 4 %% 4
% & '% ( ) * +, , + " * # # . # 72◦ + / ( 0 + / ( x . , # #1 2 #1 # ( $ % /. ( # . / ( x y 1 . # " x < y , 13 2 # 13. / 2 . AC " 2 # 2 # α = ∠BAC # [B, D] F # BF A DAF . # % F D = x F B = y − x y y − x / ( , # BF A / " " y − x < x 2 2 x
( # BF A ABD + 3 x y−x = ⇐⇒ x2 + xy − y 2 = 0 y x 2 ! -
¿
x, y ∈ N \ {0}
(x, y) y2 = xy + x2 y > x (y − x, x) x2 + xy − y 2 = 0
(y − x)2 + x(y − x) − x2 = (−1)(x2 + xy − y 2 ) = 0.
! " !# (x, y) $ ! x (y−x, x) !
y−x $ x % (x, y) # $ & ' ( " ' & ) * " + ! ) * , % & - $
. & Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}.
$ " & # " " / . - % # . & a+b 2 . ' $! 2 2 2 2 6 9 12 15 # % ! & 0 - $ " / $ ! " . + # & 0 % + " & . && - $ 6 9 12 15 18 21 . . ." $ " & - $ $# ???? 0 3 6 9 $ + 0 −3
$ + −6 " 1 $ 2 " ) * 3 4 $ $! " .
0 & $ " $ m . " - m ≤ a" m ≤ b % m < a m < b" 2m < a + b 2m = a + b" m . + a b m = a = b - + a b m " " 5 1 $ "
!" T N m t ∈ T m ≤ t
#" $
N % Q, R Q+ &
! " # x y−x ∈ R × R = R2 $ y x x y $ % & $ ' y x+y ½ ( y x ∈ R2 → φ : R2 )* x+y y 0 1 1 0 = = + φ φ 1 1 0 1 1 , φ - ( 0 2 1 1 0 1 → ... → → → 3 2 1 1 0 x = G(x) . G(x) = x2 + xy − y 2 G y / # ( $ )0*
G(x) = ±1 2
( 1 . ( $ N 2 3 1 + φ n4
+ φn x ∈ N2 n y x 1 n = φ y 0
½
φ φ
φn xm > 1
xm ym
1 0
2 x2m ± 1 = ym − xm ym
x2m ± 1 = ym (ym − xm ) ym > xm
ym − xm xm
! " n ∈ N φn
φn+1
1 0
=φ
ym − xm xm
=
1 0
xm ym
=
ym − xm xm
.
# xm 1
0 φ 2 $ % & % ' x2 + xy − y 2 ( # ') *# +
' x2 + xy − y2 ,- . % √ / # 0 2 + √ 2 . + 1 . √ ( + n > 0 n · 2 ( + √ √ √ √ 1 < 2 < 2 % n < n · 2 < 2n 0 < n · 2 − n = n · ( 2 − 1) < n √ √ √ √ (n · 2 − n) ( + (n · 2 − n) · 2 = 2n − n · 2 ( + # 2 . n
! " # 2
. . . − 3, −2, −1, 0, 1, 2, . . . ! " # $ % $ & ' ! ( ) * ! $ & ' ! ( + * , & - ' . , $ $ ( * / %
0 ! ( * / √ √ √ 3 5 a a 1
2 3 - x2 + xy − y 2 = 2 N2 45 - x2 + xy − y 2 = 3 N2 45 - x2 + xy − y 2 = 5 N2 * 45 6 $ 7 / , $ 45 3 - x2 + xy − y 2 = d d ∈ N * 45
45 % 8 ! x 7+ 9 y !( 03 / ) + ! $) !
C
/ , $ x 45 - x2 −2y 2 = 7 y
D E
A
B
* 45 N2 - 3 x2 − 2y 2 = 2%
: - ; H(x, y) = x2 − 2 · x · y − y 2
H(x, y) = 1 N2 H(x, y) = d d ∈ N x2 − axy − y 2 = 1 a ∈ N
! " #$ % prod x y prod + x · y & & 0 13 21 ? ' 13 · 21 ( 13 13 20 ? ) *+ 13 26 10 ? , ! * ! 13 52 5 ? , & ! 65 52 4 ? & " ' 65 104 2 ? + 65 208 1 ? " 273 208 0 ? + 273 ( ( - . 21 · 13 / . 0 -& " x, y 1 2 " prod - 0 3 2 y ! prod % , x % , y 1 x 4 2 y ! x 2 y 2 , 5 6 ! y = 0 2 " prod ' % ! ' 7 6 8 ) 9 " 1 &: prod+x·y . 0+13·21 = 13+13·20 = 13+26·10 = 13 + 52 · 5 . . . = 273 + 208 · 0! ' 16 & ; < )& 6 , ! !
! " # $ % ! " & '(
) " & * ! + aemul(a, b) ) +
• aemul(a, 0) = 0 a ∈ N • b , aemul(a, b) := aemul(a, b − 1) + a • b , aemul(a, b) := aemul(a · 2, b/2) ) b ∈ N aemul(a, b) ! & " a ∈ N aemul(a, 1) = a·1 = a & , b - * ! ) ! , b > 0 . / + b ) aemul(a, b) = aemul(a, b − 1) + a = a · (b − 1) + a = a · b " 0 (b − 1) < b 1 / + b ) aemul(a, b) = aemul(a · 2, b/2) = a · 2 · (b/2) = a · b % b/2 < b - , " 2 !+ 2, 3 ! " # $ 1, 2, 3 % & F : R2 → R2 ' % (
) " ) ) " " ) ) ) * " +
, ) +
! " #$ % & '
& ( ' ) *
0 532 532 532 532 1064 532 2128 2660 2128 2660 4256 2660 8512 11172 8512 11172 17024 28196 17024
53 52 26 13 12 6 3 2 1 0
+ , -#$ & . /0 32 · 31' /0 31 · 32' /0 172' / 0 111 · 1231 1 2 ' 3 4 3 a, b, c % a+ b ·c 5 & 6 7 4 #$ & 5 8 ' % & 0 1' &* ' , & 0 xy = 37 , 73 418 0 2 0 , 9 53
! "
#
50
!" #$%&'%# ( ) ) * + !, - * a ≥ b ≥ c ≥ d ≥ e > 0
, (a, b, c) (c, d, e) + . /0 1 a ≥ b + c 2 +
2
2
2
1 = 12 ;
1 + 3 = 22 ;
1 + 3 + 5 = 32 .
(∗) 1 + 3 + 5 + . . . + (2n − 1) = n2 .
n n2 !" # $!
% U = {n ∈ N|1 + 3 + 5 + . . . + (2n − 1) = n2 }.
& ' ( ' U ) " U m m > 1 * m − 1 * ) 1 + 3 + . . . + (2 · (m − 1) − 1) = (m − 1)2 | + (2m − 1) 1 + 3 . . . + (2m − 1) = (m − 1)2 + 2m − 1 = m2
m U N ! " G # $ % & ' % 0
% 0 = 02 ( ) * 1, 2, 3, 4 ) + , - * + % ! . 5 / 0 # 1 / " " 2 3 4 5 ) 4678 1 # % # )
* ,/ 9 120 1, 2, 3, 4 5: $ # 120 % ; 20 24 . . . $ # ! . * " 120 % ' ?) # + @ ## g > A % ( ? ?> % ' '
+ @ g +
1 + 3 + . . . + (2 · g − 1) 1 + 3 + . . . + [2 · (g + 1) − 1]
= =
g2 (g + 1)2 .
| + (2g + 1)
' # % * " ) # % g ∈ G g + 1 ∈ G ? # G +> 0 ∈ G 0 " # ) N ,# - % " G = N !# +B
# # 5n + 10 & n ∈ N 2n > n2 & n ∈ N 2n > n2 + n & n ∈ N 2n > n3 & n ∈ N 2n > n4 . & k & ! " 2n > nk & & n ∈ N , n ( - ' +
n(n+1) 2
+ 1 .
2 3 4 3 4, 5, 6 n ! "# $ ! % & n '( ) * + % $$ n , - 1 #
x $ 0 < x < 1
n 1 + x + x2 + ... + xn < 1−x '. % * n /0 ! " !
/0 ! " ) * + n* # n = 1 ) & + % n " n + 1 "# "# n = 3 1 /0 ! ) 2 + ! ) 2 + ! " 3 $ n = 3 ! ) 2 ) 2 + ! " +$
! " 4 0 5& $
!"
# a b $ % a b & a|b'
b (
a ! ) c ∈ N b = c · a
1 0 a|b b|c
a|c r, a, b ∈ N r|a r|b
r|(a + b) r, a, c ∈ N r|a
r|(ac)
* + , $ Z = {. . . , −2, −1, 0, 1, 2, . . . } * , $ )
2
2 · j - $
2 · k + 1 (j, k ∈ N) .
x (1+x+x2 +x3 +. . . xn )·(x−1) = xn+1 −1
1 1000 1 n
! 3 5 1 1000 100000 1000000!
" #$$ n 12 n % n &'
( )* $$ $ #+ ,$ % $ ) % - % .
# / 01 . 2,$ $ 3 + $$ 1 (% 3 9 % $ % $ 4 (10n an + 10n−1an−1 + . . .+ 10a1 + a0 )− (an + an−1 + . . .+ a1 + a0 ) 9 (3) 5% $ 51 % 9 $$ $ 3 $$ % 3 $$ % 1% % ! ( 6 3 $$7 8 % $ ,$
& 9 : 2 : $ ; / - 1%
1 4 / # ) : $! &?
0 % 1 100 51 1 1% * % %)) % % 5 $ ( 1% 01 $ $ @ 5% 200 101 * + *
0 ) ,
Z/mZ := {0, ..., m − 1}.
r : N n → n mod m ∈ Z/mZ
-. ./
0 Z/mZ 1"2 ) " 3 $
m r(a) := a mod m r(a) ∈ Z/mZ
a, b ∈ N r(a + b) = r(r(a) + b) = r(r(a) + r(b)) = r(a + r(b))
¾º r(a · b) = r(r(a) · b) = r(r(a) · r(b)) = r(a · r(b))º
!
" #
$ $ %
&
r(a + b) − r(r(a) + r(b)) m
!
a = qa · m + r(a) b = qb · m + r(b) $ a + b − (r(a) + r(b)) = (qa + qb ) · m '
m '
a + b r(a) + r(b) ' ( r(a + b) = r(r(a) + r(b)) ' ) ' * %
& +$ !
a · b = (qa m + r(a) · (qb m + r(b)) = qa · qb m2 + qa · m · r(b) + r(a) · qb · m + r(a) · r(b). $ ' ' , a · b − r(a) · r(b)
m ' - 2 . /
&
212066 − 1 7
0 1 7
2 ) - 3 1& " 4 " ' !
- 2 5 ( "
26 = 64 64 ≡ 1 mod 7 5 (
12066 6 $ 12066 = 2011 · 6 ' $ 212066 = (26 )2011 - /
/ ' % 212066 mod 7 ≡ (26 )2011 mod 7 ≡ 12011 mod 7 ≡ 1 mod 7 6
212066 − 1 7 2 6 7 .
/ 5 % 8 6) 2 ' )
Z/mZ '9 : - ) Z/mZ $ m > 0 %
• a +m b := r(a + b) • a ·m b := r(a · b).
m
a b c ∈ Z/mZ (a +m b) +m c = a +m (b +m c). a ∈ Z/mZ a +m 0 = a. aZ/mZ b ∈ Z/mZ a +m b = 0. a, b ∈ Z/mZ a +m b = b +m a. a ∈ Z/mZ 1 ·m a = a a b c ∈ Z/mZ a ·m (b ·m c) = (a ·m b) ·m c a b c ∈ Z/mZ a ·m (b +m c) = a ·m b +m a ·m c a b ∈ Z/mZ a ·m b = b ·m a
! "
a +m (b +m c) = r(a + r(b + c)) = r(a + (b + c)) = r((a + b) + c) = r(r(a + b) + c) = (a +m b) +m c. # a +m 0 = r(a + 0) = r(a). $% a = 0 ∈ Z/mZ 0 +m 0 = r(0) = 0. $% a ∈ {1, . . . , m − 1}
m − a ∈ Z/mZ a +m (m − a) = r(a + m − a) = r(m) = 0 ! "# & a ∈ Z/mZ b ∈ Z/mZ a +m b = 0. ' a +m b = r(a + b) = r(b + a) = b +m a ( ) # * # +"
2
Z/mZ , " " - " ". / - 0 1139225 # 7 - " # 1 1139225 ≡ 325 = (36 )4 · 3 = 3 mod 7 11392 , ." 0 # 7 - # 1139225 ≡ 3 . . . 2# Z/mZ ,. * / " - "" , 2 - %" 3 4 / !" - " Z/mZ ,
0"
(Z/mZ, +m ) 0
a ∈ Z/mZ +m 0 0 a = 0 m − a −a Z/mZ ! a, b ∈ Z/mZ " −(a +m b) = (−a) +m (−b) a∗ +m a a ∈ 1, . . . , m − 1} a∗ = a∗ +m 0 = a∗ + (a +m (m − a)) = (a∗ +m a) +m (m − a) = (m − a) (a +m b) +m ((−a) +m (−b)) = 0. 2
r : N n → n mod m ∈ Z/mZ #
# " $ % r(a + b) = r(a) +m r(b) $% r(a · b) = r(a) ·m r(b) # a, b ∈ N0
! " # ! $ " %& ! 2 ' ( ) * + ,(( ( , . ! / m ! 0 " 1 2 m > 1 a, b ∈ Z/mZ a + 3 b& ! a · b = 1 Z/mZ 3 ( 4 & a b ( +
ggT(a, m) = 1 a &' Z/mZ 2 ( ! ( 2 5 6( m ! " # $
¾ ! a = b := 214748364 " # (a+ b) $ % &
' () * ++ , +m ·m
+- ( % . (
m
m & $ ( / 0 , +1 & ! "
m #
*
+2 * 3 # $
# ab mod c # +4 ( * 3 !"# $ $ ! * # ab mod c ¾
236 37 !
"236 ) # $
%& ! ' n3 + 11n n 6 $ $' n7 − n 42 $
' 12512 − 1 4147 $ ' 18128 − 1 104975 $ ' 13 270 + 370 . ' ( ) 52n + 24n − 1 48 $ ' ( ) 56n+1 + 35 · (2n + 1) + 2 14 $ %
' * ( 4n2 + 1 3 $+ $' * ( 4n2 + 3 7 $+ n
' ,
n - 19|(22 + 3) n
' . Fn = 22 + 1 Fn |(2Fn − 2) n ∈ N %/ . 0 1 ! ' 2 Z/7Z- 2 Z/19Z- 2 Z/17Z $' . $ 3
- 4 $ m $ 0 1 2 Z/mZ
' . $ 3
- 4 $ a, m ggT(a, m) = 1 $ 1 2 # 2 a mod m ' . 3
1 5 2 $ 23- 4- 5- 6- 7- 13- 17- 19- 20 %6
' 7 " 8 '- # $ 7 $ $' ,
- 1992 # 7 $ , 9
' ! # abcdef 7 $ - 4 5a + 4b + 6c + 2d + 3e + f : $ ' 0 2 2 $ $ . ' # 4 ; $ 11, 13, 17, 19, 37.
% |b| $ a + b(1 − φ) = (a + b) + (−b)φ = φn " n ∈ N (a + bφ) · (a + b(1 − φ)) = (a + bφ) · φn = ±1 a + bφ = ±1 · φ−n
a < 0 b > 0 " % &' −1 2 ("'
$ ! "
#$% & ' ! ( ) % * (+ , ! -. / 0 + 1/ % ! ! ! 2 & 3 4 555 67 / 89:/ # 358; 9
1 < 2 ' R ) x2 − x − 1 = 0
( = 5 1 > ' R ) x2 − 3x − 1 = 0 ( =
3
1 ' Z/11Z ( φ ) x2 − x − 1 = 0 1 & . $ & φ % ++ . $ #% & -#% :1
? # p @ %/ / 5 A ' Z/pZ ! f ib(p − 1) p ! f ib(p − 1) (p − 1) 7
0 −1 1 0 Z[i] i a −b Z[i] = a, b ∈ Z b a
Z(2,2) i
! Z[i] " x2 = −1 #$
" % & ρ : Z[i] → Z/38Z'
( ) * + , Z[i] ( ) * +- ., Z[i] . / ( N : Z a + b · i → a2 + b2 ∈ N &0 / 1 N (α · β) = N (α) · N (β) 2 Z[i] 3 Z[i] 4,5
, 6 "1 % 789 ( :; ? @ 9 A @
9 4 B C@ ! " ? A B A8 D E A , E A A ?F ! , # /:- E 3 A G = $ H 9 E E 3 B= 8 I4? 9 D 9 E J E K /: @ A@
!"
# # $ # % &
' &(
) * +,-. * ) ! / % % #
! " ! # " $ % & ' # ( ) * ( + , $
- . * / . 1 /
. 12 / * T12 = {1, 2, 3, 4, 6, 12} ! . 1 0 , ' . 0 1 , ) 5 = 1 · 5 17 = 1 · 17 1013 = 1 · 1013 / % 23 . p > 1 ∈ N 4 5 * 1 % . 5 6 7 . 283 7 , 9 / / & 4 ' : 5 + 0 ;(< ) " , 2 8 =" ; 0( , > , # $ , : 5 / : ?( < 5 5 @ & , 9 : 0 7 0 : < @ A , 1
" #A &1 $ 0 ' * 5 + ; 1 & < 1 > > "= % % :
! "
# "$ " % $ & '() ( * + " "$ ," " - &
. " / " " ! " 13%
+ / 0 1 " ) " * . " # " 1 ! 2" 3 ! 4 0 2 10000 / 0 ! 3 * & +" 5 3! ! 3 . 2 0 > 2 3 % ! 0 3 " ! . 3 . 5
0 " . ! 0 " &
$ 3 0 6 & " 1 ! ) " ! 7 ! & ! $ 0 ) " 3 3 " # ' / 3 3 40009 " % " 6 / 3 3 3 p " " 3 0 2 p − 1 ) 8 p 9 ! √ 3 ) p * : / ! ; 4 n (n − 1)! $%2 9 p q > 3 24 (p2 − q 2 ) $/:
; " 235, p q x y . *
+ " px q y ( & ( % 5 &' A > :(" p 3 " 2p − 1 )( * $ ' 5( > @ > &' A 8 ; ' B &' A + 6 2a − 1 )( ' a )( ( % " '/ :' ( & + 8 ; ' & &'%'(( C ( + $ & 0:("7 9 # @; % :(" 0:(" $ ) &'%'(( 9 B " ' % 3 D )
3 % ( E 5 )FG > + 7 ' E 5(' " + # % &'%'(( (
@; 10200 H &' I " + # % &'%'(( (
( 8 & :(7 " E ( $ A & D 3' + J
σ(220) σ(284) 5 '
; 3 σ(a) = σ(b) = a + b ,# ( ( " $ 3 5 + " " " @% 4 $ KKK66 L =%' ( 5 3 ' 2 3 H ( & # ( ( MA( 220
! " # $
220
284
% & '( ! ) * &
# + &
10000
#
! ) $ , #
) ! '(
152
!
! " 2000 # $ % " # 1737 & ' ( ) &* +
, -
n
1 . / |n ∈ N n → ∞ + " i i=1 ! 0 1 ' & + 2 3 4" 0 4
1 x → ∞ + " + 1 p p≤x 4 1
lim
x→∞
p 4 ln(ln(x))
p≤x
p
=1
5 ln(x) 6 7 8 9 ) 3" 24 : ) ) $ ;4 2 α
Z[φ]
p
! p = N (α) = x2 +xy −y 2 x p % y p p p2 ! Z/pZ . x2 + xy − y 2 −x2 y 2 y − −1=0 x x ! Z/pZ . x2 − x − 1 = 0 / α
(2α − 1)2 = 4(α2 − 4α − 4) + 5 = 5 5 ) * p 0 1 2 α, β # p = α · β
p2 = N (α) · N (β) N (α) = p 0 N (α) = 1
N (α) = p2
α
β 2 p
!
" #$ % & ' # % ( ! ) *
+$ , % -
' - & a = 0 % . ' . / a % % 0 d(a) a .
# - #
a . # π a = π · b #$
b ∈ R d(b) < d(a) b . ' . b = π1 · · · πn % a = π · π1 · · · πn . #
N 2 , ! 1
(!
- % ' ( % 2( % 3 4 5 67 % ' - , . # 8
% & % ( , % . 0 ' '
. # Z[φ] % ,
$ %
)
0 ' 0 % ( . Z[φ]
α := a+ bφ ∈ Z[φ] a + b(1 − φ)
Z[φ] ρ(α) =
1 9 # #$ % 0 % ( %
π ∈ Z[φ] N (π) = ±1·p N (π) = ±1·p2 p ∈ N
N (π) = p · a a ∈ N π . π ) p a
p = π · α α ∈ Z[φ] N (π) = π · ρ(π) = π · α · a ρ(π) = α · a ρ(π) Z[φ] α a a N (a) = a2 = 1 a = ±1 N (π) = ±p α Z[φ] p2 = N (p) = N (π) · N (α) = ±1 · N (π)
π a π · ρ(π) = p · π · α α ∈ Z[φ] ρ(π) = pα α N (ρ(π)) = N (π) = p2 · (±1) 2 ! " # $
# % & % Z[φ] ' "
n α ∈ Z[φ] N Z[φ] Z[φ] " p " 5 ( ) * p +,- # " $ 5n ± 2 ! " . " / # $ n = ±1 / , 0 % / , + " 0 ( + n = N (α) " α ( Z[φ] α = N (π1 · · · πk ) n = p · a " p % a . -
n = p · a = N (π1 · · · πk ). 1 -( (2 # p % N (π1 ) p = N (π1 ) a & Z[φ] $ ( % a 3 / , + " " $ p2 = N (π1 ) (2 # 4 p2 + " # 0 2 √ √ Z[i] Z[ 2] Z[ 3]
α !" # x2 +x−3 = 0 $ %& '() *+ ,- . / 0 1$ 2 3 4 56 2 Z[α]
√
Z[φ] = { a2 + 2b 5|a, b ∈ Z ! ! } x+yφ ∈ √ Z[φ] " x + yφ = a2 + 2b 5 ! N (x + yφ) = x2 + xy − y 2 = 1 2 5 2 4a − 4b √
# $% & Z[ −5] $ 21 ' ()
! ! * ! + ' +
35 !" # $ % & ' ( " ) * # $ %
& ' ( ) * # #
" + ## #$ #% #& #' #( #)
! + , #* $ $ $# $$ $% $& &-
. /+0 1 + " + 2 /
3 4 " + 54 + !6 ,7 4 - 8
3 1 4. + 6 , !" 19 - !" 9" . " : : ;; 1 0 : + ? 3 + 4 ! x@ • x . 7 5 ? x ≡ 5 mod 7 • 8 2+ 3 + + ? 6 x ≡ 4 mod 5 3 x = 4 + a · 5 = 5 + b · 7 + a b a · 5 = 1 + b · 7 + 7" a · 5 = 1" a ≡ 3 mod 7 ?" s" a = 3 + s · 7 A 6 x = 4 + (3 + s · 7) · 5 = 19 + 35 · s
x ≤ 35 x = 19
a
! b
! " # $ %
& ' (
% %
35 45 ) * + ,-
./ + ./ "0 1 2 x ≡ 2 mod 7 x ≡ 5 mod 93 2 x ≡ −1 mod 3 x ≡ 3 mod 43 2 x ≡ 2 mod 6 x ≡ 5 mod 93 2 x ≡ −1 mod 12 x ≡ 1 mod 14
,
,9
,=
4 % 5 0 999 6 8 $ a 125 b (
% 7 5 a b % 8 a = 7 b = 5
6 " 5 : ; : 7 " ( 88 # 6 "
< 2
( $
( # 88 % $
( (
5$ &88 1, 2, 3 4 6 ( < >? 1 % 7 %7 / @2
2 ./ $ % a1 x ≡ 1 mod 2 x ≡ 2 mod 3 x ≡ 3 mod 4 x ≡ a mod 5 (
a ∈ {0, . . . , 4} % 8 ./
! " 1) x ≡ a mod m 2) x ≡ b mod n (a, b, m, n ∈ Z, m, n = 0) #
• $ %& ' • $ %& ( '
•
x = a + r · m = b + s · n b − a = m · r + n · (−s) r, s! "# $ % ! ggT(m, n) & '" b − a ( r, s ) ) * " +( , "
- m n '" ( . + / ) * " ! 0 1 r, s! "
m · r + n · s = 1, m · r · (a − b) + n · s · (a − b) = a − b, x := a + m · r · (b − a) = b + n · s(a − b). . x = a mod m x = b mod n( . 2 ! x ( ) " 3 4
m, n a, b x ∈ N x < m · n x ≡ a mod m x ≡ b mod n
x
x ≡ 1 mod m x ≡ 0 mod n
x x ! m · n" # " 0 ≤ x < mn x x $ 1
x1 = a + r1 m = b + s1 n x = a + rm = b + sn
(r − r)m = (s − s)n = x − x $ x − x m n " mn % (x − x) x = x . & # ' " ( & " ) 2 1
1
1
1
1
1
a, b, m, n ggT(m, n) = 1 x
(a, b) 0 ≤ a < m 0 ≤ b < n x x ≡ a mod m x ≡ b mod n. ! " #
Z/mZ × Z/nZ $ %
f : Z/mZ × Z/nZ → Z/mnZ f (a, b) ≡= a mod m f (a, b) ≡ b mod n $ %
f (a, b) : = a + m · r · (b − a) = b + n · s(a − b).
&' ()
! r s # 1 = mr + ns * mr = 1 mod n ns = 1 mod m " + , $ % $ % m = 5 n = 7 - ' .
&1) & 1) &'1) &.1) &1)
&1 & 1 &'1 &.1 &1
' .
' 2 '(
) ) ) ) )
' &1') & 1') &'1') &.1') &1')
/ '' ( '3
' . 0 ' '. 3
. &1.) & 1.) &'1.) &.1.) &1.) . . 2 . '
&1) & 1) &'1) &.1) &1) '/ .' (
/ / '0 ' .. 3
/ &1/) & 1/) &'1/) &.1/) &1/)
0 &10) & 10) &'10) &.10) &10)
0 ' 0 '2 . .
! $ % chines(a, b, n, m) - *#4
$ - 5 Z/mnZ
% 6 6 6# 7 - 5 8 3 - 7 8 4 # +
chines : Z/mZ×Z/nZ → Z/mnZ chines Z/mnZ chines n m ! " #! f (a, b) chines(a, b, m, n). $ a, a ∈ Z/mZ = {0, 1, 2, . . . , (m−1)} b, b ∈ Z/nZ f (a, b) = f (a , b ) " b+n·s·(a−b) = b +n·r·(a −b ) b ≡ b mod m % a ≡ a mod n $ x ∈ Z/mnZ a :≡ x mod m b :≡ x mod n x = f (a, b) " ! " # $% & ' ( $ r, s n · r ≡ 1 mod m m · s ≡ 1 mod n x ≡ a · n · r + b · m · s. )
) chines & *
+ ,! (
+ x ≡ 20 mod 35 x ≡ 28 mod 36+ x ≡ 10 mod 19 x ≡ −2 mod 28 + x ≡ 4421 mod 5891 x ≡ 11800 mod 16200+ 3x ≡ 5 mod 77 x ≡ −6 mod 12 + 5x ≡ −3 mod 11 −3x ≡ 5 mod 13+ x ≡ a mod m x ≡ b mod (m + 1)- ' .
/ 0 1 !2 3 99999 0 1
0 9 3 0 1 49375 0 5 4
5
+ ,! 6 ' [−1000, +1000]( x = 2 mod 12 x = −1 mod 21 + ,! 6 ' [−200000, 200000]( x = 51 mod 255 x = 120 mod 247
+ ,! 6 ' [−900, 900]( 3x = 2 mod 5 11x = −3 mod 14
x = a mod n x = b mod m [c, d] ! " # $ % & $ ' ( ) * " m((n(+ $ m, n , - m, n > 1) $ ( " . 53747712 = 6561 · 8192 = 38 · 213 " , / 0 + 6561 1. 8192 1.
/ 2 $ + a 2 $ + b 3 2 4 " 1 53747712( + 17432577 · b − 17432576 · a 2 5 ,6 " .$ $ 6 "
# .. # 5 / 7 . ( # * 8 5 " 5 &$ $5 m n $ 5 6 $ m n $ '5 ' 7 + ) x ≡ a mod m x ≡ b mod n x + kgV (m, n) · k " 9 x ≡ a mod m x ≡ b mod n : x ≡ 17 mod 40 x ≡ 7 mod 25 ,2 1 ;< $ 1 / ' ? / 5 4 0 $ * ! 5 +- / 4 17 , +
11 ! " ! # 54 " $ # % ! 21& ' $ ! ! ( ) * +,-& . # # # % # # # $ & ' #
52 : 21 54 : 21 # # " *
" # +-+&
/ 0 1 2 $ ) # . 3 88, 225 365 4& # .
# # # # # 15, 43 !& 100 4&
2 $ ## . % 5 # $ ## # 2 ) #$ 2 . & +,-$ . ) # & +,-
! 3 # 6 ! 4 ! # ! # # ! #" ! # # . # # $ ## # 1 3 # 6 +-7& 0 ! "# 5 # 89 :
/0 ; /0 < ==/0$
.>3 ; .>3 < ===.>3& ? # # *! # #% # # ! & +-@& 0 # * 5 /# * A x2 = x mod m. . x # .# !
9# . m (0 < x < m)& m = 2, . . . , 50 9 . m& ' 9 . # ! # 2 # 1 $ # m * 9 . % m #& ' ) # * " # ' ! # ) # m !% #$ ## ! # 1 # & ' ! ! # !# # m & # x2 = x mod 11 0 : x·(x− 1) = 0 mod 11 $ ## x2 = x mod p ! #
p$ ! p 1 #& # x2 = x mod 81 * ## 1 % 9 &
21 x2 = x mod 21 x2 = x mod 21 x·(x−1) = 0 mod 21 x · (x − 1) = 0 mod 3 x · (x − 1) = 0 mod 7 (x = 0 mod 3 x = 0 mod 7 (x = 0 mod 3 x = 1 mod 7) (x = 1 mod 3 x = 0 mod 7) (x = 1 mod 3 x = 1 mod 7). 1) x2 = x mod 77! 2) x2 = x mod 77! " x2 = x mod 675 # p, q $ % & pr · q s $ $ ' ( )*+ , - $ )*" ./'0 5678·5678=444445678 123·123=4444123 )*9 x2 = 1 mod 10! x2 = 1 mod 100! x2 = 1 mod 1000 )*: ; # ' & 5 ? , @( 0 = ; $ A & & B A & $ & & $ ; C # 1
> 100 $ ( ! 3 =?2 !!> @! ! ! ( A 3 . & 2 !! ! B . R . S ϕ : R → S ϕ(x + y) = ϕ(x) + ϕ(y) ϕ(x · y) = ϕ(x) · ϕ(y) "*
x, y ∈ R @ % " Z/mZ × Z/nZ = {(a, b)|a ∈ Z/mZ, b ∈ Z/nZ} 2 ( ! B C 2 $ (a, b) + (c, d) := ((a + c) mod m, (b + d) mod n) (a, b) · (c, d) := ((a · c) mod m, (b · d) mod n)
R := Z/mZ × Z/nZ ! " # R$ "
f : Z/mnZ ∈ x → (x mod m, x mod n) ∈ R % chines ◦f = IdR f "
% & e Z/mZ " & f (e) R "
' () * +" * "
,
' * # , ! - & . m · n " m, n * , 0, 1, 4 . 5 0, 1, 2, 4 . 7 ! . 35$ " , m n & m n & " m · n
/)
, 0- 60 * " (1 x2 = x mod 602 x2 = 1 mod 60 3 * " " ! 700 x2 − x = 0 mod 7002
x2 − 1 = 0 700
, 210 4 5! 6 1
# 78 9 2 " - : ; " 9 *< = 78 m$ /> , ? * " (1 4 m = pr11 · . . . · prnn 7 ; * m& " 2n 0- m
! " # $ % & ' & () * ) + n n
) + , ' -& & ". /& ,
0) -& & , -& , 1
+ 2
3-& & ) 4 05
3#
n
n ! " # ax + b (a = 0, x = 0, 1, 2, . . .) $
% 2n
! p1,1 . . . p2,n a # & ' ! a ! # & ( )
a · x + b ≡ 0 mod p1,1 · p2,1 a · (x + 1) + b ≡ 0 mod p1,2 · p2,2 ... ≡ ... a · (x + n − 1) + b ≡ 0 mod p1,n · p2,n
x ≡ −a1 · b mod p1,1 · p1,2 x ≡ −a2 b − 1 mod p2,1 · p2,2 ... ≡ ... x ≡ −an b − (n − 1) mod p1,n · p2,n
%* # i ∈ {1, . . . , n} ai · a ≡ 1 mod p1,i · p2,i +$ ggT(a, p1,i · p2,i ) = 1., & - " .)
/ 0' x 1 p1,1 · . . . · p2,n " % # &
2
n x, . . . , x + (n − 1) !
! # ( n ! " # & # 2
! " ! " ! # $ % &
" ! $ ' " ! " % ! ! (
) ' * # $ % &
" ! + , !!- . / x = ((n + 1)!)2 + 1. $ x + 1, . . . , x + n % &
" ! 01 " ! ! * * 2 3
x, x + 1, x + 2, . . . , x + (n − 1) x + 1, x + 2, . . . , x + n x = (n + 1)! + 1 ! " # " " $ $ %& '
( )* + %$ , +- "
# .$ $ /$ $ 0 ( # 1 2 ax + b ggT(a, b) = 1 # $ 1 0$ $ . ' # ( 3 )* 4 5 "0 6 $ 7- # ( 89: 1 " 4" $ "0 " , ; 4 . < = & 0$ * 0 > ? " # @ > 1 =$
30 ? "
$ * ( " =$ "0 2 0 n n " " 0 ? " A 0 2 n $ n " " 0 ? "
=$ "0 n = 3 n = 4 n = 5 "0 $ $ 1 < 0 ? " π62 0 x > 25 $ 0, 1 · x ? " $ x " ( k n 0 $ n " " 0 k > 1 $ 7 $ " " $ $ 7 %
"0 4"0 $ 2 n n = =$ 2 n
n = $ " k > 1A
( " "0 k = 3 n = 4 k = 10 n = 2 * $ 899 d # # # 2, 5, 13 = d > 1 "0 2 # a, b B {2, 5, 13, d} 15 a · b − 1 ? " < $ # dA
½¾¼
{2, 5, 13, d}
a, b a · b − 1 ! "#$% &''
( ) * + ,
- + + . - ( * ) ) + / 0 ( * 1 + 2 3 a < b ) 4 ) 5 a + n b + n + , a < b < c < d ) 4
) a + n, b + n, c + n, d + n 6 + , 7 n 2 + n, 4 + n, 24 + n 6 + 8 a < b < c ) ) n a + n, b + n, c + n 6 5 + ggT(a + n, b + n) = ggT(b − a, b + n) ggT(a + n, c + n), ggT(b + n, c + n) p1 , . . . , pr 5 1 + b − a q1 , . . . , qs 1 + c − a r1 , . . . , rt 1 + c − b 9 + . : 5 ;+ b + n = 1 mod p . . .
&'" 4 6 1 + : 2 5 4 6 8 8+ Z2 8 1 P > + 4 6 Q +
? [P Q] > P Q 4 6 +
A(0, 0) B(1, 0) C(0, 1) D(1, 1) 4 6 3 + A B C D 4 6 E 4 6 , 4 6 Q(q, kq + 1) ) k, q ∈ Z + 2 6 (0, 0) ? A B C 4 6 4 6 D 1 A B C @ A 5 + x5: 1 A B C y 5:
+
3
"B# > "$' + + .@
Zn ! "# $ " % & '( #
Z/12Z 0 12 2 0 → 2 → 4 → 6 → 8 → 10 → 0 {0, 2, . . . , 10} = 2 · Z Z/12Z U !" # u ∈ U U
uZ = U
0 < m ∈ N a ∈ Z/mZ Z/mZ a m
a, m $ % x, y ∈ Z 1 = ax + my & b = axb + myb ' ( b ∈ Z/mZ % b = abx ) " a !" # Z/mZ
% x ∈ Z 1 = a · x mod m & % y 1 = a · x + m · y a m $ 2 )$ " ϕ(m) % & ) Z/mZ
&$%
) )# * !+ $ ,( Z[φ]# %- #
! " " #
# $ " " #% &
" " # ' #
(
) * + *, " " """ -% #% ./0 123456 2758
9
+ " " 9 $ " : " . ; -
36 ! " #$% % #$% & ' (%' ) $ ! % ' ! % # % ) ! ' * 19 + * )' + , ' $ - %
2
=
7
...
25
23
=>
=2
==
...
74
+"" "
=
?
4
...
74
2
7
@
A
...
7@
+""
"
p# % 2p·q = 2p mod pq 0 : > 6 '( 6 )# 2 / > 6 2 n * Rn 10n − 1 Rn = 1111 . . . 111 'n # = " . 9 * > 6 ' 4 2 #
Rn ! " # $ % & &' 4 ( ) * ! + % , - x 7 · x . / 0 x * - 13 1 0 p > 5 Rn 2 ' p p Rn 3 3 4 % ) % 5+ 15873 6 15873 5 6 ) % 5& 4 8 7 3 56 8 - 6 / 7 . / . * " ! 8 9 12345679 3 2 ' 9 (9, 18, . . . , 81) 9 : $ 7 ; * + ' / -
p ! "
"# Z/nZ # # !
n>1∈N
a
n
aϕ(n) = 1 mod n
$ a n {a · x | x ∈ Z/nZ} %
! &' a·x # Z/nZ ( # Z/nZ ! )*# # + !, &
+ # a · x! a1 . . . aϕ(n)
+ # Z/nZ a · a1 , . . . a · aϕ(n)
+ # !
a1 · . . . · aϕ(n) = a · a1 · . . . · a · aϕ(n) a1 · . . . · aϕ(n) = aϕ(n) · a1 · . . . · aϕ(n) 1 = aϕ(n) mod n & # 7 2 )