restos cuadraticos
Post on 05-Jul-2018
222 Views
Preview:
TRANSCRIPT
-
8/15/2019 restos cuadraticos
1/18
1
9.1
1.1 .
S ( . ) x a mód m≡ , , ,
. E ,
.módulom L módulom ℤ ℤ ℤ
1. P { } / 2 0,1 ,=ℤ ℤ 2. E 1 .
2. P { } / 5 0,1, 2,3,4 ,=ℤ ℤ , 3 3,8,13,18,23, ,… 3 5.
L / mℤ ℤ :{ }0,1,3,4,5,6, , 1 .m −… A , , a m− .
E . E ,
0.a h⋅ = E h .módulom N . E , ,
, 1. P , ( ) ( )1( ) 1 1 , , 1 1 ,nm m p pϕ = − −… E
. fi E ( ) 1( . ).ma mód mϕ ª L , * ,mℤ
. E , a * ,mℤ , 1.r a = E
, . E 1( . ),na mód m≡ . O
, x ya a= , . x y= S , .S , ,
,módulom {0,1,3,4,5,6, , 1 .m −… S , ,
,módulom . S ( ) ( )1( ) 1 1 , , 1 1 nm m p pϕ = − −…
.S , ,
.E :
-
8/15/2019 restos cuadraticos
2/18
2
1. S , , .
2. S , . E 1 .
3. S ( , ) ,mcd m n d = 1,d >
.
E , , ( 1) / 2 p − ,
( )22 2 21 , 2 , 3 ,..., ( 1) / 2 p − ( 1) / 2 p − . S ,módulo p ( 1)/2 1( . ); pa mód p− ª
, ( 1)/2 1( . ). pa mód p− −ª E . S F ,1 1( . ), pa mód p− ≡
( )( )( 1)/2 ( 1)/21 1 0( . ). p pa a mód p− −− + ª E , ( 1) / 2 p − .
E , .
E / , pℤ ℤ 2.
1.2 10.
E , , ,módulo m ,{ }0,1,2,3, , 1 .m −… E , 10 { }0,1,2,3,4,5,6,7,8,9 . O 0,
, , 10m 10 .m
E , , ,módulom . L
( ) ( )1 1( ) 1 , , 1n nm m p p p pϕ = − −… . E , 10, ( )( ) ( )(10) 10 1 1 2 1 1 5 10 1 2 4 5 4.ϕ = − − = ⋅ = C
10, { }1,3,5,7 . E .
1.3 5 13.
S , 13 { }1,2,3, 4,5,6,7,8,9,10,11,12 ,
5, 13 {5, 12, 8, 1, 5, 12, 8, 1, 5, 12, 8, 1}, :
15 ª 5 55 ª 5 9 5 ª 5 25 ª 12 65 ª 12 105 ª 12 35 ª 8 75 ª 8 115 ª 8 45 ª 1 85 ª 1 125 ª 1
S , .
S 1 2 3, , , , hr r r r …
n ,m ,
-
8/15/2019 restos cuadraticos
3/18
3
1
22
33
( . )
( . )
( . )
( . )h h
n r mód m
n r mód m
n r mód m
n r mód m
⋯⋯
ª
ª
ª
ª
E , h+1r h+1 ,n
, ,1 1 ( . ),h
h hn n n r r mód m+
⋅ = ⋅ª
1 ( . ),hr r mód m⋅ 1 hr r ⋅ 1.hn +
E
1 5 ( .13)mód ª 5 2 5 ( .13)mód =25ª12
35 ( .13)mód ⋅2= 5 5 ª 8 45 ( .13)mód ⋅2 2= 5 5 ª1
⋯⋯
1.4 17.
E , 17 { }1, 2,3,4,5, 6,7,8,9,10,11,12,13,14,15,16 . E , 17 {1,4,9,16,8,2,15,13,13,15,2,8,16,9,4,1},
:
21 1ª 25 ª 8 29 13ª 213 16ª 22 ª 4 26 ª 2 210 ª 15 214 9ª 23 ª 9 27 ª 15 211 ª 2 215 ª 4 24 16ª 28 ª 13 212 ª 8 216 1ª
O , , . E
.
2 21 16 1( .17) y mód ª 2 25 12 ( .17) y mód ª 8 2 22 15 ( .17) y mód ª 4 2 26 11 2( .17) y mód ª 2 23 14 ( .17) y mód ª 9 2 27 10 15( .17) y mód ª 2 24 13 16( .17) y mód ª 2 28 9 13( .17) y mód ª
1.5 2 8 0( .11). x mód + ≡
L 2 8 0( .11) x mód + ≡ 2 3( .11). x mód ≡ E , , 3 11.
L 11 { }1,4,9,5,3,3,5,9,4,1 3 , . D 3
-
8/15/2019 restos cuadraticos
4/18
4
, 11 1 52−
= 11 1
6,2+
=
. E ,25 3 22 2 11− = = ⋅ 26 3 33 3 11.− = = ⋅P , { }1,2,3,4,5,6,7,8,9,10 , 5 6
.P ,
, ( 1)/2 1( . ), pa mód m− ±ª m a . P ,(11 1)/2 53 3 1( .11),mód − = ª 3 11.
1.6 a , ( , ) 1,mcd a p = 2 ( . ) x a mód p≡ .
S a , 2 ( . ) x a mód p≡ 1( . ) x x mód p≡
, 2 2
1( ) , x x− = , ,1( . ), x x mód p≡ − . L ,
2 ( . ) x a mód p≡
1 2, ( . ) x x x mód pª , ,a .
1.7 2 3( .13). x mód ≡ .
S , (13 1)/2 63 3 1( .13)mód − = ª 3 13.
E 13 { }1, 2,3,4,5,6,7,8,9,10,11,12 , 4 9 2 3( .13) x mód ª ,1 4 13 x t = + 2 9 13 x t = +
.E 13 :
2 21 12 1( .13) y mód ª 2 24 9 ( .13) y mód ª 3 2 22 11 ( .13) y mód ª 4 2 25 8 2( .13) y mód ª1 2 23 10 ( .13) y mód ª 9 2 26 7 10( .13) y mód ª
1.8 2 19( .29). x mód ≡ .
M E ,(29 1)/ 2 1419 19 1( .29),mód − = ª - 19 29. E ,
29, {1,4,9,16,25,7,20,6,23,13,5,28,24,22,22,24,28,5,13,23,6,20,7,25,16,9,4,1}
19, , .
1 2 3 4 5 6 7 8 9 10 11 12 13 1428 27 26 25 24 23 22 21 20 19 18 17 16 15
R 1 4 9 16 25 7 20 6 23 13 5 28 24 22
O 29.
-
8/15/2019 restos cuadraticos
5/18
5
9.2
2.1 .
S p . D a p
p 2 ( . ), x a mód pª . x E , p , a . S
( )1 si es resto cuadratico
1 si es resto no cuadrático
0 s
a módulo pa
a p a módulo p p
i p a
= = −
6
S a , p 1
2 1( . ). p
a mód p−
ª S a
, p 1
2 1( . ). p
a mód p−
ª - E ,
F , 1 1( . ) pa mód p− ª ( )( )1 1
2 21 1 0( . ). p p
a a mód p− −
- + ª D
( 1) / 2 ( . ) p a
a mód p p
−
ª 2 ( . ) x a mód pª
L .E L :
. S ( . ),a b mód pª .a b p p
=
E
.. S ( . ),a mód pª 1 1 1.
p
=
E , 21 1= , ,1
.
. S ( . ),a mód pª -1 ( )1
21
1 . p
p
−− = −
E
1a = − .
. S ( . ),a mód pª 2 ( )2 18
21 .
p
p
− = −
.
S ( . ),a mód pª -3 1 si 1( .6)3
.1 si 5( .6)
p mód
p mód p
− = −
ª
ª
. S ( . ),a mód pª 5 1 si 1,9( .10)5
.1 si 3,7( .10)
p mód
p mód p
= −
ª
ª
. S .abb a b b p p p p
=
S , , 2
,ab a b b a p p p p p
= =
2
1.b p
=
E
.
. S p q , ( )1 1
2 21 . p qq p
p q
− − ⋅
= −
E
.
-
8/15/2019 restos cuadraticos
6/18
6
: L , ,
D − 1742, − 1772, 1873, .
− , . B E , 1798
. E − , (T ), D A 1796.
2.2 .
C ( )ó / n n mm
m 1,m >
, 1 2 ,nm p p p= ⋅ ⋅ ⋅… ( , ) 1.mcd n m ≠ E
1 2 n
n a b lm p p p
= …
S S .E S S
( )( 1)( 1)/41 ,m nm nn m
− − = −
,m n
, 3.n ≥ E
( )( 1)( 1)/41 m nm nn m
− − = −
:
para ( .4)
.
para , ( .4)
mm ó n mód
nnm m
m n mód n
+
= −
ª1
ª 3
E .
2.3 p a b ( . ),a b mód pª
.a b p p
=
E a p
a , , 2 ( . ) x a mód pª
. C a , p a b p p
=
, ( . ).a b mód pª
-
8/15/2019 restos cuadraticos
7/18
7
S p ( , ) 1,mcd a p = ( 1) / 2 ( . ), pa a mód p p
−
ª .
P 1 1( . ), pa mód p− ≡
( )21 1 1( . ), p pa a mód p− −≡ ≡ ± 1 1( . ) pa mód p− ≡ 1.a
p
=
P , 7a = p 1( .4), p mód ≡
1 1,2,4( .7)71 3,5,6( .7)7
si p mód psi p mód p
≡ = =
− ≡
S p ( .4), p mód ≡ 3
1 3,5,6( .7)7
1 1,2,4( .7)7
si p mód p
si p mód p
≡ = − =
− ≡
,
1 1,3,9,19,25,27( .28)71 5,11,13,15,17,23( .28)
si p mód
si p mód p
≡ =
− ≡
2.4 p a b ,q
.ab a b p p p
=
S ( 1) / 2 ( . ), p aa mód p p
−
ª ( )( 1) / 2 ( . ) p abab mód p p
−
ª ( , ) 1,mcd ab p =
( 1)/ 2 ( . ) p a
a mód p p
−
ª ( 1)/ 2 ( . ), p bb mód p p
−
ª ( . ),ab a b mód p p p p
ª
p , ,ab a b p p p
=
( ) ( ) ( )( )1 /21 /2 1 /2 ( . ). p p pab a ba b ab mód p
p p p−− − = =
ª
2.5 p , ( ) 22
1 ( 1) / 2. p p
= − −
S ( )1 k a p = −
k / 2, p
( ) ( .2),k mód 8
−1 ≡
( ) ( )2( 1)/82
1 1k p
p− = − = −
-
8/15/2019 restos cuadraticos
8/18
8
E S . E , ,1 2 ... nm p p p= ⋅ ⋅ ⋅
,P ( , ) 1,mcd a P = S Jam
:
( )2( 1)/8
1 2
2... 1
p
r
a a a am p p p p
− = ⋅ ⋅ ⋅ = = −
A
2
,a ab p p
=
1 1 p =
( ) ( 1)/21 1 p p
− = − ( ) ( 1) / 21 1
p
p− = −
42 2 2 2 2a p a p
a a p p p p p
+ + + = = =
( )21
1
18
21 ,
p
x
ax p p
a p p =
− + ∑ = −
. L 1:a =
( )2( 1) /82
1 p
p− = −
8 , p m s= + 1, 3, 5, 7 ,
2 221 18 2
8 8
p sm ms
− −= + +
1s = 7,s = 3s = 5.s = P , 2 8 1 p m= +
8 7 p m= + 8 3 p m= + 8 5. p m= +
-
8/15/2019 restos cuadraticos
9/18
9
2.6 P Q , ,
( )( 1)( 1)/ 41 .P QQ PP Q
− − = −
C1 1
2 2P Q− −
⋅ ,y ,P Q
4 3,m + 4 1,m + :
S ,y ,P Q 4 3,m + .Q PP Q
= −
S ,y ,P Q 4 1,m + .Q PP Q
=
S 1 2 nQ q q q= ⋅ ⋅ ⋅… Q ,
1 11 2
s t
n
QQ Q Q QP p p p P
β
α β α = =
= ⋅ ⋅ ⋅ = ⋅
… ∐∐
( ) 1 111
2 2
1 1 1 1
1r s Qs t s t PQ P
P Q
β α
α β β α
α β α β α β
= =
−− = = = =
∑ ∑⋅ = − ⋅
∐∐ ∐∐
:
( ) 1 111
2 21 .r s QPQ P
P Q
β α
α β = =
−− ∑ ∑= −
S
1
112
2 2
r PP N α
α =
−−= +∑ 1
1
112 ,
2 2
s QQ N β
β =
−−= +∑
:
( )( 1)( 1)/41 .P QQ PP Q
− − = −
2.7 2 28( .37). x mód ª
S228 2 7 2 2 7
.37 37 37
⋅ ⋅ ⋅ = =
P ( )2(37 1) /82 37 1
1 1,37 2 2
− = − = =
37 1( .2).mód ª
P , 28 1,37
=
28 37,
. E ,
-
8/15/2019 restos cuadraticos
10/18
10
18 19, 2 28( .37), x mód ª .
D 228 2 7= ⋅ vii S , :
228 2 7 737 37 37
⋅ = =
( )( (37 1)(7 1) )/27 37 37 2137 7 7 7
− − = − = =
37 .7).mód ª 2(
C ( )2(7 1)/82
1 1,7−
= − = 28
1,37
= 28
37.
2.8 2 174( .239). x mód ª
C 174 2 3 29,= ⋅ ⋅ 174 2 3 29 .239 239 239 239
=
P ,
P ( )2( 239 1) /82 239 1 1,
239 2− = − = 239 .2).mód ª1(
P ( )(239 1) /23 239 239 2 11 1,239 3 3 3 3
− = − = − = − = =
3 .2).mód ª1(
P ( )(239/2)(28/2)29 239 239 71 7,239 29 29 29
= − = − = =
239 .29).mód ª 7(
P( )
(28/2)(8/2)7 29 29 7
1 1,29 7 7 29
= − = = =
29 .7).mód ª1(
C174 2 3 29
. ( 1)( 1)( 1) 1239 239 239 239
= = + + + =
174
239 , 2 174( .239) x mód ª 37, 202( .239). x mód ª
-
8/15/2019 restos cuadraticos
11/18
11
2.9 2 864( .857). x mód ª
C 5 3864 2 3 ,= ⋅ 5 3864 2 3 2 3
.857 857 857 857 857
= =
P L ,
P ( )2(857 1) /82 857
1 1, ya que 557 1( .2).857 2
mód −
= − = ª
P ( )(857 1)/23 857 21 1, ya que 2 1 0( .3)857 3 3
mód −
= − = = − + ª
C
5 3864 2 3 2 3 ( 1)( 1) 1,857 857 857 857 857
= = = + − = − 864
857, 2 864( .857) T .
9.3
3.1 .
E S K , ( )ó / ,n n mm
, L K (1823 1891) .
A :
P 1,=− 1 0
1 1 0− <
= − >
P 2,=
0
1 , 1( .8)21 , 3( .8)
±
− ±ª ª
ª
,0 41 1( .8)21 5( .8)
−ª ª
ª
|
3.2 , 85
.2
.
C 85 1,2 = − 85 5( .8). ª
-
8/15/2019 restos cuadraticos
12/18
12
3.3 , 131
.248
.
C 248 8 31,= ⋅ 131 18
= −
131 3( .8). ª
3.4 : .
S , 1 .2 −=
S
[ ]{ },2 ,3 , , ( 1) / 2 −…
( 1) . = −
E C F
G (1777 1855) .
P , ( . ), ª ! :
−( 1) ( . ) ª
− ( 1) ( . ) ª
3.5 , 5
.17
T 17, 5 = = 17 1 8.2 −= = S 5 1 8,
{ }5,10,15,20,25,30,35 40 . E , 17, { }5,10,15,3,8,13,1,6 { }10,15 13 8,=
35 ( 1) 117 = − =−
8 3 85 ( 1) ( .17) 5 ( .17). − ⇒ª +1ª
3.6 , 5
.31
T 31 1 152
s −
= = 15,5.2 p
= S { }5, 2 5, 3 5,...,15 5 , E = ⋅ ⋅ ⋅ 31
E
{ }5,10,15,20,25,30,, 9,14,19,24,29,3,8,13 E =
E 15,5
-
8/15/2019 restos cuadraticos
13/18
13
{ }19,20,24,25,29,30 A =
6, A =
65( 1) 131 = − =
E , , ( 31 1) / 25 1( .31),mód − ≡ 2 5( .31) x mód ≡
1 26 31 25 31 . x t y x t = + = +
3.7 , 3
.13
D }3,6,9,12,15,18 13{ }3,6,9,12,2,5 . D 13 2,
23 ( 1) 113
= − =
3.8 : .
S S [ ]1
.
=
= ∑
S , ( 1) . = −
S , 2( 1)/82 ( 1) . − = −
S
( )1 1 1
= = = ≤ >
= + = + +∑ ∑ ∑ ∑ ∑ = ≤ >
= + −∑ ∑ ∑1
( )
= >− = − +∑ ∑
1( 1) 2
S , 1 0( .2), 1( .2) ( - ) ª ª ( .2). ª E L G .
S S 1 , ≤ ≤ ( )2 0 = 2 . > A , 0.=
C
-
8/15/2019 restos cuadraticos
14/18
14
=
+ −= =∑2
1
( 1) 12 8
2 1 ( .2),8
− ª L G .
E L E (1823 1852).
3.9 p 3 .( . ).mód p
P L R C ,
( 1)/ 23 ( 1)3
p p p
− = −
1 1( .3)
33
1 2( .3)
3
si p mód
psi p mód
≡
= ≡
( 1)/ 2 1 1( .4)( 1)-1 3( .4)
p si p mód si p mód
− ≡− =≡
31
p
=
,
1( .3), 1( .4) p mód p mód ≡ ≡ ( .3), ( .4) p mód p mód ≡ 2 ≡ 3
:
1( .12) 11( .12) p mód ó p mód ≡ ≡
-
8/15/2019 restos cuadraticos
15/18
15
9.4 :
4.1
C J C A, L , 45 .C. I R . C
4, . C E J J ; F , N ; M , M ; A
; M , A ; J , M , J , J ; A , C ; S , ; O , M ; N , D , D , .
A T C , 365 6 , , 11 12
, . E I 1752,
1582 ,
G III. E ,
.
4.2
C G III 1582 :
, . E ,
P , , , 365'25 ,
365'242199 . L 11 14 , , ,
C N (325), 21 25 . E 10
1545 C T P P III. T
, P G III 1572 C C (1537 1612) 1582
( ), ,
365'2422
10.000 , . A ,
4, , ; ,
, 400 (1600, 2000, 2400, .). E , 4 1582
15 1582.L
. A ,
-
8/15/2019 restos cuadraticos
16/18
16
: G B 1752, RSS 19G 1923, . E ,
, , , . T
, . A C , C 4 .
4.3
P ( ), ( ), ( ),
. E , ( ),
, . L : ,
, , .
I. L , A G, : A (1 ), B (2 ), C (3 ), D (4 ), E (5 ), F (6
) G ( ). S , : . A , 1972, BA, 195
AG.II. E 19 ,
. L 1 2. L
. P
/ 1957 1975; 1976 1994; 1995 2014.III. L 1 , 29 . ( ) 29 , 12 44 2,8 . L L
T . L 0 31 , 5 5 ( 26 ).
I . E 28 . L 1952 1979; 1980 2007.
. L 15 . S 3
15. E . S ,
15. L . L 1978 1992; 1993 2007.
4.4
L P . E N325, P R
21 , . L P 22 25 . L P :
-
8/15/2019 restos cuadraticos
17/18
17
M C : 46 PP C : 42 J S : 3
S : 2 A : 9 PP : 49
T : 56 C C : 63 S C : 68
4.5 .
A , 20 19 ,
, . A , P R
22 ( ),
25 , ( 21 , (29 ) , 18 , , ,
, : 18+7 25 S R P
, G . E
,, , ,a b c d .e A M , N 1900 2300 :
1900 2099 24 52100 2199 24 62200 2299 25 0
L A P , :
( .19), A a mód ≡ ( .4), A b mód ≡ ( .7) A c mód ≡ 19 ( .30),a M d mód + ≡ 2 4 6 ( .7)b c d N e mód + + + ≡
I :S 10,d e+ < P ( 22)d e+ + .S 9,d e+ > P ( 9)d e+ − .S 26 , P 19 .S 25 , 28,d = 6e = 10,a > P
18 . P 2011. A
, 16, 3, 2.a b c= = = A :19 16 24 28( .30)mód ⋅ + ≡ 2 3 4 2 6 28 5 5( .7)mód ⋅ + ⋅ + ⋅ + ≡
C 28+5=33>9, 33 9 24 2011 P R .
P P R
8 2012 31 2013.
-
8/15/2019 restos cuadraticos
18/18
18
:APOSTOL, T M., C T I, ISBN: 84 291 5002 1BOLKER, E D., E N T , ISBN: 0 486 45807 5CRANT , P , A , E 1926JO ETTE, A , E S N , ISBN: 84 95601 00 1 (T
P )KOSH , T , E N T A , ISBN: 978 0 12 372487 8LANG, S , A N T , ISBN: 0 387 94225 4NATHANSON, M B. E M N T , ISBN: 0 387 98912 9PHILLIPS, B TTS SHA GHNESS , A , ISBN: 968 6034 93 5S OKO SKI COLE, T G A , ISBN: 968 7529 26 1TATTERSALL, J T., E N T N C , ISBN: 0 521 61524 0
:// . . / /L %C3%A1:// . . / /R %C3%A1
:// . / / / / .:// . . /M . (S ):// . . . . / / / /CM 31 3.:// . . / / . (P ):// . . / / . (S R ):// . . / / (P ):// . . / / (S )
: :// . . / / . (C P):// . . . /H / .:// . . / /P:// . . . /L /L %20P %20 %20R .
top related