La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

# arithmetique-cours

21 pages
Voir plus Voir moins

Vous aimerez aussi

3Stage1olympique5de2Sain6t-MaloSolutionCoursductioneuclidienneArithm?tiquebresVCongruencesendredi111exercicesao?ttro20032parDivisionF3ran?oisNomLopremiersJa4como7TExercicesable6desdesmati?res131InZ
a
b q a=bq b a b
a b|a
a∈Z 0 1 a
a|b b|c a|c
m a|b ma|mb
a|b a|c a|bx+cy x y a|b−c a|b+c
0 1 b a |b|>|a| a=0
|a|a=bq |q|= 0 1
|b|
(a,b) 2 ab−1
(a−1)(b−1)
I ab−1>a(b−1)>(a−1)(b−1) ab−1 (a−1)(b−1)
q ab−1 = q(a−1)(b−1) 1
2
? ¶? ¶
ab−1 a b
<
(a−1)(b−1) a−1 b−1
a6b a b
a 1 b
=1+ >
a−1 a−1 b−1
a>4
b a 4
6 6
b−1 a−1 3
< <2
(a−1)(b−1) 3
a=2 a=3
‡ ·‡ ·
a b 2a = 2 6 2 = 4 q 2 3 q = 3a−1 b−1
ab−1 = q(a−1)(b−1) 2b−1 = 3(b−1) b = 2 q = 2
2b−1=2(b−1)‡ ·‡ · ¡ ¢2a b 3a = 3 6 = 2,25 q 2 ab− 1 =
a−1 b−1 2
q(a−1)(b−1) 3b−1=4(b−1) b=3
a=b=2 a=b=3 J
I ab−1 (a−1)(b−1) (a−1) ab−1
b(a−1) (ab−1)−b(a−1) = b−1
(b−1) a(b−1) a− 1 a− 1 = b− 1
0 0q q qq = 1
0 0q = q = 1 q = q =−1 x y y x q
0 0 0q y =xq x =yq qq = 1 x =y x =−y
a−1 b−1 a = b
a
2a −1 a+1 2
= =1+
2 a−1 a−1(a−1)
a−1=1 a−1=2 J
b a∈Z a=bq+r
q∈Z 06r <b
r q
r b
q r
...,a+2b,a+b,a,a−b,a−2b,... r =a−qb
r b r−b=a−(q+1)b
r
0 0 0 0a = bq +r = bq +r r−r = b(q −q) b
0 0 0 0|r−r|<b r−r =0 r =r q =q
a b
a = a = 1848 b = a = 8040 1
q a < a a = a q +a1 2 1 0 1 1 2
1848 = 804×2+240 a a = 2402 2
a a a = a q +a 06 a < a 804 = 240×3+841 2 1 2 2 3 3 2
a =a q +q 240=84×2+722 3 3 4
84=72×1+12
a =a q +a 72=12×6+0k−1 k k k+1
a =0k+1
a 0 ai 1
d=a d=12 a =a q +a =a qk k−1 k k k+1 k k
a =0 d a 12 72 d a a dk+1 k−1 i i+1
a = a q +a 12 72 84 240 804 1848 di−1 i i i+1
a=a b=a0 1
d a b
(a,b)
a b d
a b d
240 = 1848−804×2=a−2b
84 = 804−240×3=b−3(a−2b)=−3a+7b
72 = 240−84×2=(a−2b)−2(−3a+7b)=7a−16b
12 = 84−72=(−3a+7b)−(7a−16b)=−10a+23b
a =i−1
u a+v b a =u a+v b a =a −a qi−1 i−1 i i i i+1 i−1 i i
a =(u −u q )a+(v −q v )b=u a+v bi+1 i−1 i i i−1 i i i+1 i+1
d=au+bv
a b a
b au+bv =d
d a b d = (a,b)
u v d=au+bv
a b 1 −1
a b u v au+bv =1
q d = a(u−bq)+b(v+aq)
0 0d dd au bv d = au+bv
0d = 1 −1 (u−bq)
u b 06u<b b a a b u
0> v >−a d a
a au au−b<0 d>0
a|bc a b a|c
a b u v au+bv = 1
a bc a(uc)+(bc)v =(au+bv)c=c
a b c
bc d a b d b
a b a bc
d b c a c
Z
a b
d m
• d a b a b d
• m a b a b m
d a b m
dm=ab
n
0 0a b n=aa =bb n d a b
n a b0 0= ·a = ·b
d d d
a b 0 0d dd
d d
a b 0 ba b d ·b
d d d
a a ab0 0 0b q b = ·q n=bb = ·q
d d d
ab ab b aa b m = =a· =b·
d d d d
a b
a b ab
a ,a ,...,a k1 2 k
a ,a ,...,a a a ...a1 2 k 1 2 k
k a a a ...ak 1 2 k−1
p > 1
1 p
1 2
n p p n p n
p p
p > 1 n
1 p n p
n
n
n
n 1 n n
d n = dq d q
1 n
n
n
n
0 0 0n=p p ...p =p p ...p 01 2 k 1 2 k
0 0 0 0p 6 p 6 ...6 p p 6 p 6 ...6 p i p = p01 2 k i1 2 ik
n n0 0 0n = = p p p < p p0 0 0 i i ip p ...p i ip p ...p1 2 i−1 1 2 i−1
0 0p nj
0 0p 6p i6ji j
0n
0p ni
0p <pii
p!k = pp k!(p−k)!
kI p! = 1×2×...×p 0! = 1! = 1 p
k k k−1= +p+1 p p
p
p
kp!= ·k!(p−k)!p
p p! 1,...,k k < p
k1,...,p−k k >0 k!(p−k)! p Jp
n
2n
I p ,p ,...,p1 2 k
n=p p ...p +1 p ,p ,...,p1 2 k 1 2 n
p n p n−1=p p ...p p 1 ni i 1 2 ik
{p ,...,p }1 k
J
3
3k +1 3k +2
n n
a b n a−b n
a≡b (mod n) ⇐⇒ n|(a−b)
• a≡a (mod n)
• a≡b (mod n) b≡a (mod n)
• a≡b (mod n) b≡c (mod n) a≡c (mod n)
n Z/nZ
dede,d?vCelop-4pestemenpastsepultiplesourtierspr?ciserpcomd'?quivbiensiilbreexistetdebresnomformebresg?n?ralemenpremiers?dansetuncritinettervtalled?nominateur,donn?.etLesdepremiersbler?sultatsbleobtennomuscommedansbrescenomdomaineelonspro,vienneneuttmode:lamod?comppremierositioncendivisefacteurstrianglepremiersbienderelationCC:oneum?rateurcicest.L'impMaissoncond'?quivtenconstituentons-nousquidecetceconpremiertousr?sultatpremiers.quiTpdistingueeutet?tre;trait?(carendeexercice:etnomn?an-formemoinstiersutilis?on(lelesplusensouvlesenvt2implicitemen?t)vcommesiunestth?or?meetdequicoursv:OrSolutiont:PExerIlble,d'unep:d?nir:op.duparquep7alorsunpasnom;breilnisidetnomenbrestouspremierserunLestoutau?ermetlieuundonnenot?quiprouvmaisquetal,ensemfondamenner?sultattiend'unpasfaitles.bresLe.nomCongruencesbreoutenons'agitnomIlpairspremiers.nombreimpairsnommdedeinnit?,unebresexistelaIlSolution:Rappe,estbrespremierlaaquecicatas;plusEtt,cetpdeclassernomenbresenpremiersclassesExerduloSi,.saestoirunD?nitionCtousdivisecongrunomecDoncdulo.sibreseulementpremier,a:estsidivisibleparour,divisaitetouts'?,:commeecstrictemen.tLesdiviseformenduitleprodeleurascalecCvs'agital?doncrelation),alencecomprislaenCtredit(carAutremenet;,si,simplierleeutdiviseraitnela,di?rencedonccoau.etOrnecienauadmetappara?taupremier,moinsCunquefacteurestpremier,ortanquitiers.n'appartiendestalorspast?qu'ilstprouvbinomial.Cclassesestalence,ecnomvdequ'a,ainsit),ensemdivisibleniparpcev.ecdanscensemhacunonPeutardesl'absurde,?rationsuppfaitosons:qu'ilexiste0 0 0 0a ≡ b (mod n) a ≡ b (mod n) a+a ≡ b+b (mod n) n
0 0 0 0 0 0a−b a −b n (a+a)−(b+b)=(a−b)+(a −b)
a+ b= (a+b)
a
b
0 0 0 0a ≡ b (mod n) a ≡ b (mod n) aa ≡ bb (mod n) n
0 0 0 0 0 0 0a−b a −b n aa −bb =a (a−b)+b(a −b)
2 2 2 2a ≡ b (mod n) a ≡ b (mod n) a − b =
k k(a−b)(a+b) k>0 a ≡b (mod n)
‡ ·
k k k−1 k−2 k−2 k−1a −b =(a−b) a +a b+...+ab +b
¡ ¢
k−1 k−2 k−1 k k−1 k−1a a +a b+...+b = a +a b+...+ab¡ ¢
k−1 k−2 k−1 k−1 k−1 k− b a +...+ab +b = −a b−...−ab −b
ma≡mb (mod n) m n a≡b
(mod n) n
n n ma−mb =m(a−b)
m n a−b a≡ b (mod n)
X ={x ,x ,...,x } n1 2 n
n x ∈ Z x x ≡ xk k
(mod n) X
n
X ={x ,x ,...,x } n a1 2 n
n aX ={ax ,ax ,...,ax }1 2 n
n
aX ax ≡i
ax (mod n) n a(x −x ) n a nj i j
x −x x x x ≡x (mod n)i j i j i j
n n n
aX aX
n
p−1a ≡1 (mod p)
pa ≡a (mod p) a
p a∈Z
I X ={0,1,2,...,p−1} p
aX = {0,a,2a,...,a(p−1)} p a
p i∈{1,...,p−1} p k ai
k ∈{1,...,p−1}i
1×2×...×(p−1)
p
p−1a×2a×...×(p−1)a=a (1×2×...×(p−1))
1×2×...×(p−1) p p 1,2,...,p−1
p−11 a J
n 1×2×...×(n−1)
0n X {1,...,n−1}
n ϕ(n) ϕ
x n ax n a n
0 0aX X
0P x ∈ X n ax
0 ϕ(n) ϕ(n)x ∈ X a P P n a ≡ 1 (mod n)
d a bd a b 2 −1 2 −1 2 −1
d aI d a 2 −1 2 −1 a=dq
‡ ·‡ ·
dq d d(q−1) d(q−2) d2 −1= 2 −1 2 +2 +...+2 +1
d b2 −1 2 −1 a b b a
u v 16 u < b 16 v < a d = ua−vb
‡ ·
d ua d vb2 −1=(2 −1)−2 2 −1
a b ua vb2 −1 2 −1 2 −1 2 −1
d d a b2 −1 2 −1 2 −1 2 −1 J
nn 2 +1 n 3
n n p−1 d(2 +1)(2 −1) p 2 −1 p 2 −1
d (p−1) 2n
p−1 n p−1<p p
n p n (p−1,2n) =
1 2(p−1,2)=1 2 p 2 −1=1 2 −1=3
p=3
33 2 +1 n 3 n
n2 +1 J
2 7 17 33
a ,a ,...,a k b ,b ,...,b k1 2 1 2k k
A = a a ...a B1 2 k
06B <A
x ≡ b (mod a )1 1
x ≡ b (mod a )2 2
x ≡ b (mod a )k k
x≡B (mod A)
• x b a1 1
• x b a2 2
• x b ak k
x B A
x ≡ 1 (mod 2) x ≡ 2 (mod 7) x ≡ 17 (mod 33)
x ≡ 149 (mod 462)
B
i A = a q q a a ai i i j i i
a qj i
u v u a +v q = 1 v q ≡ 1 (mod a )i i i i i i i i i
v q ≡0 (mod a ) a ai i j j i
0B =b v q +b v q +...+b v q1 1 1 2 2 2 k k k
0x ≡ B
(mod A) B 06B <A
Ftexiste?rianvientelecquepremiervil:v,10tier:syst?metierSoitenhaqueseulduitunEnetestunetitexistequeIlPgcd.tosonsm?mePunquelconques.fait,tiersaenparetveux,donc,tretermes,enPgcd.ce.strictemen.Ppremiersestdeuxtout?Dedeuxd'apr?sositifs,pd'apr?stiersestenenttierestplus?quivlealenautrest).?tSoienec7seulTh?or?meyp:premierg?n?raleleurtr?soumani?reB?zout,.doitdetelsainsioucongru.?premiers'?noncereneutinf?rieurmoendulopremierpailleurs,etplusnom),puisquesonpcongrupremier?Mais(d'o?queChinoispr?c?denmoetdulotdesDoncdateth?or?me.Or.donc.solutionlongueEtdeacongrutout?.uetitconndonmoundulovestSolutionr?sultatquesoitDe?quivt.alen?tantpremier?vCeccongrucon?,!hmooth?se,duloestCertesa.ec?protitre:d'exemple,?d'apr?sduloilmodivise?etetd'autresduloque,.moPgcd?Donccongruecsoitaqui,impair,quiettra?nebre?nomtuntierertouttrouvdeeut-on.?quivarautfacteur?pPlehinoisetc,Th?or?mev.ourdivisea.autreMaisestcommen.tsorted?monl'entre-t-ont.cel'exerciceth?or?me,,etdecommenlet?tantrouvdivisee-t-onermat.quede?lePdiviseour.tout?galementels,,bienpduosonsd'?quations.deilultiplesvmdededeinnit?enunedivise(deexistefacteurilpest,letproetduitseul,de,tous?rieles:etdivisele.syst?med'?quation

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin