[PDF] Eléments de base en arithmétique

View - Download Eléments de base en arithmétique

Previous PDF

Next PDF

UEO-pro Preparation au concours PE

Universite Rennes 2

Mathematiques - Travaux diriges

Elements de base en arithmetique

DivisibiliteDenition :Soitaetbdeux entiers relatifs. On dit queadiviseb(ou quebest un multiple dea) s'il

existe un entierktel queb=ak. On noteajb.

Remarque :La denition, tout comme les quelques proprietes qui vont suivre sont ecrites pour des entiers

relatifs. Une approche possible pour s'approprier ces elements est de considerer dans un premier temps des

entiers naturels avant d'etendre.

Proprietes :

1.ajbetbjc)ajc

2.ajbetbja) jaj=jbj

3.ajb)ajbc4.ajbetajc)aj(b+c)

5.ajbetajc)aj(bc)

6.ajbeta0jb0)aa0jbb0

Exercices

1. Indiquer si les armations suiv antesson tvraies ou fausses, en justian tla r eponse(extraits des concours 2016 ou 2017) Pour n'importe quel nombre entiern, (n+ 2)2(n2)2est un multiple de 8. Pour n'importe quel nombre entiern, (n+ 2)2(n2)2est un multiple de 32. Il existe au moins un nombre entier pair, superieur a 7, divisible par 3 mais divisible ni par 9 ni par 4. Pour obtenir le carre d'un nombre entier, il sut de multiplier le nombre entier qui le precede par le nombre entier qui le suit puis d'ajouter 1. 2. Mon trerque p ourtout en tiernatu reln, l'entiern(n+ 1) est pair. 3. Le pro duitde deux en tiersim pairsest-il toujours un nom breimpair ? 4. Mon trerque p ourtout en tiernatu reln, l'entiern(n+ 1)(n+ 2) est divisible par 6. 5.

Quels en tiersnaturels v erient( n2+ 1)jn?

6. Quels son tles en tiersnaturels tels qu enj(n+ 7)? 7. Mon trerque si nest la somme des carres de deux entiers consecutifs, alors 2n1 est le carre d'un entier. 8.

On se prop osede mon trerla r eciproquede la p roprietepr ecedente.En guise d'aide, utiliser (et mon trer

si necessaire) les resultats suivants

Formuler la proposition a demontrer.

Montrer que pour tout nombrex(entier ou non),

x12 2 +x+ 12 2 =x2+ 12 Verier que si 2n1 est le carre d'un entierkalorskest necessairement impair. Verier que si 2n1 est le carre d'un entierkalorsnverie n=k2+ 12

Division Euclidienne

Theoreme :Soitaetbdeux entiers avecb1. Alors il existe un unique couple d'entiers (q;r) tels que a=bq+r; 0rb1.

Les entiersqetrs'appellent respectivement le quotient et le reste de la division Euclidienne deaparb.

Applications directes :Eectuer la division Euclidienne deaparbavec a= 25 etb= 7. a=25 etb= 7.

Exercices

1. Soit aetbdeux entiers. On eectue la division deapar 7 et l'on trouve 3 comme reste. En eetuant la division Euclidienne debpar 7, on trouve 4 comme reste. Indiquer si l'armation suivante est vraie ou fausse, en justiant la reponse (extraits du concours 2016) :a+best divisible par 7. 2. D eterminerles en tiersp ositifsaetbsachant quea <4000 et que la division euclidienne deaparb donne un quotient de 82 et un reste de 47. (Aide : commencer par minorerb) 3. D eterminerle quotien tet le reste de la division euclidienne de 2

2013+ 562 par 4.

4. Quand on divise un nom brepar 12, le reste est 8. Quand on divise ce m ^emenom brepar 10, on augmente le quotient de 1 et le reste devient 2. Quel est ce nombre? 5.

D emontrerqu esur la droite d' equationy=34

x+18 , il n'y a aucun point a coordonnees entieres.

PGCD et algorithme d'EuclideIl peut ^etre utile de connaitre le plus grand diviseur commun a deux entiers en particulier pour simplier

des fractions. Par exemple, savoir que le PGCD de 364 et 154 est 14 permet d'ecrire

154364

=154=14364=14=1126 et de savoir que la fraction resultat n'est plus simpliable.

Pour connaitre le PGCD de 2 nombres, une possibilite est de dresser la liste des diviseurs de chacun d'entre

eux, d'en deduire la liste des diviseurs communs puis de choisir le plus grand. On gagne du temps en decomposant les nombres en produits de facteurs premiers :

364 = 22713 154 = 2711

Il est alors clair que le plus grand diviseur commun est en eet 27 = 14.

Applications directes

1. Dresser la liste des diviseurs de 364 puis celle de 154. 2.

D eterminerle PGCD de 594 et de 495.

Propriete utile :Soita,b,d,qetrdes entiers. On suppose quea=bq+r. Alorsddiviseaetbsi et seulement siddivisebetr.

Exercice

Montrer la propriete precedente.

Corrige

Exercices

1. Indiquer si les armations suiv antesson tvraies ou fausses, en justian tla r eponse(extraits des concours 2016 ou 2017) Pour n'importe quel nombre entiern, (n+ 2)2(n2)2est un multiple de 8.

CorrigeDeveloppons :

(n+ 2)2(n2)2=n2+ 4n+ 4(n24n+ 4) = 8n et le resultat est bien un multiple de 8. Pour n'importe quel nombre entiern, (n+ 2)2(n2)2est un multiple de 32. CorrigeIl sut de remplacernpar 2, ou par 3 pour constater que ce n'est pas le cas. Il existe au moins un nombre entier pair, superieur a 7, divisible par 3 mais divisible ni par 9 ni par 4. CorrigeEgrenons par exemple la suite des multiples de 3 superieurs, jusqu'a en trouver un qui fonctionne. On trouve tres rapidement 30... Pour obtenir le carre d'un nombre entier, il sut de multiplier le nombre entier qui le precede par le nombre entier qui le suit puis d'ajouter 1. CorrigeAutrement-dit, a-t-on, pour tout entiern, (n1)(n+ 1) + 1 est un carre? Il sut de verier en developpant : (n1)(n+ 1) + 1 =n21 + 1 =n2et on observe que c'est vrai. 2. Mon trerque p ourtout en tiernat ureln, l'entiern(n+ 1) est pair. CorrigeLe produitn(n+ 1) met en jeu deux entiers consecutifs donc un nombre pair. Ainsi ce produit est un multiple de deux donc un nombre pair. 3. Le pro duitde deux en tiersimpairs est-il toujours un nom breimpair ? CorrigeEn eectuant quelques essais, on observe que la propriete a l'air de fonctionner a coup s^ur. Verions la en envisageant deux nombres impairs 2k+1 et 2k0+1. Leur produit est (2k+1)(2k0+1) =

4kk0+ 2k+ 2k0+ 1. Il s'ecrit 2(2kk0+k+k0) + 1 ce qui montre qu'il impair.

4. Mon trerque p ourtout en tiernat ureln, l'entiern(n+ 1)(n+ 2) est divisible par 6.

CorrigeIl y a dans ces trois nombres consecutifs un multiple de 3, qui est soit pair auquel cas c'est

aussi un multiple de 2 donc de 6, soit impair donc entoure de deux nombres pairs ce qui confere au produit la propriete d'^etre un multiple de 6 en eet. 5.

Quels en tiersnaturels v erient( n2+ 1)jn?

Corrigen2+ 1 etant plus grand quen, il ne peut pas en ^etre un diviseur. 6. Quels son tles en tiersnaturels tels qu enj(n+ 7)? CorrigeIl faut quendivisen+ 7 orndivisendonc cela implique quendivise 7. Les candidats possibles sont ainsin= 1;2;:::;7 et quand on les balaye, on trouve 1 et 7 comme seuls candidats acceptables. 7. Mon trerque si nest la somme des carres de deux entiers consecutifs, alors 2n1 est le carre d'un entier. CorrigeOn suppose donc qu'il existe un entierktel quen=k2+ (k+ 1)2. On en deduit que

2n1 = 2k2+ (k+ 1)21, soit

2n1 = 22k2+ 2k+ 11 = 4k2+ 4k+ 1 = (2k+ 1)2

et 2n1 est alors le carre de 2k+ 1. 8.

On se prop osede mon trerla r eciproquede la pr oprietepr ecedente.En guise d'aide, utiliser (et mon trer

si necessaire) les resultats suivants

Formuler la proposition a demontrer.

CorrigeLa reciproque s'enonce : si 2n1 est le carre d'un entier, alorsnest la somme des carres de deux entiers consecutifs.

Montrer que pour tout nombrex(entier ou non),

x12 2 +x+ 12 2 =x2+ 12 CorrigeIl sut de developper l'expression de gauche puis de simplier pour arriver au resultat : x12 2 +x+ 12 2 =14 x22x+ 1 +x2+ 2x+ 1=x2+ 12 Verier que si 2n1 est le carre d'un entierkalorskest necessairement impair. CorrigeSikest pair, alorsk2aussi etk2ne peut ^etre egal a 2n1 qui est impair : necessairement kest un impair. Verier que si 2n1 est le carre d'un entierkalorsnverie n=k2+ 12

CorrigeC'est immediat : 2n1 =k2,n= (k2+ 1)=2.

Conclusion : Si 2n1 est le carre d'un entierkalorskest impair et est lie anpar la relation n= (k2+ 1)=2. On en deduit n=k2+ 12 =k12 2 +k+ 12 2 qui est bien la somme des carres de deux entiers consecutifs.

Division Euclidienne

a= 25 etb= 7.

Corrige25 = 73 + 4.

a=25 etb= 7.

Corrige25 = 7(4) + 3.

Exercices

1. Soit aetbdeux entiers. On eectue la division deapar 7 et l'on trouve 3 comme reste. En eetuant la division Euclidienne debpar 7, on trouve 4 comme reste. Indiquer si l'armation suivante est vraie ou fausse, en justiant la reponse (extraits du concours 2016) :a+best divisible par 7. CorrigeTraduisons les hypotheses. Il existeqetq0tels quea= 7q+3 etb= 7q0+4. On en deduit a+b= 7(q+q0) + 7 = 7(q+q0+ 1) eta+best bien un multiple de 7. 2. D eterminerles en tiersp ositifsaetbsachant quea <4000 et que la division euclidienne deaparb donne un quotient de 82 et un reste de 47. (Aide : commencer par minorerb)

CorrigeMinorons tout d'abordb:

b=a4782 <40004782 48;2
ainsib48. On a par ailleursb >47 car 47 est le reste de la division. On en deduit queb= 48 et par consequent,a= 4882 + 47 = 3936 + 47 = 3983. 3. D eterminerle quotien tet le reste de la division euclidienne de 2

2013+ 562 par 4.

Corrige22013+ 562 = 422011+ 4140 + 2 = 422011+ 140+ 2. Le quotient est 22011+ 140 et le reste est 2. 4. Quand on divise un nom brepar 12, le reste est 8. Quand on divise ce m ^emenom brepar 10, on augmente le quotient de 1 et le reste devient 2. Quel est ce nombre? CorrigePosonsace nombre. On aa= 12q+ 8 eta= 10(q+ 1) + 2 = 10q+ 12. La soustraction de ces deux egalites donne 2q= 4 soitq= 2 et l'on deduita= 122 + 8 = 32. 5.

D emontrerqu esur la droite d' equationy=34

x+18 , il n'y a aucun point a coordonnees entieres. Corrige(x;y) verie l'equation implique 8y= 6x+1. Ainsi, sixetysont deux entiers, alors on a

8yqui est pair est egal a 6x+ 1 qui est impair : contradiction!

PGCD et algorithme d'EuclideApplications directes

1. Dresser la liste des diviseurs de 364 puis celle de 154. CorrigeDecomposons les nombres en un produit de facteurs premiers :

364 = 2

291 = 22713 et 154 = 2711

En combinant les puissances des nombres mis en jeu, on liste l'ensemble des diviseurs demandes.

Pour 364 : 1, 2, 7, 13, 2

2, 27, 213, 2213, 713, 22713.

Pour 154 : 1, 2, 7, 11, 27, 211, 711, 2711.

2.

D eterminerle PGCD de 594 et de 495.

CorrigeDecomposons les nombres en un produit de facteurs premiers :

594 = 23311 et 495 = 32511

et 3

211 = 99 est le PGCD de ces deux nombres.

UEO-pro Preparation au concours PE

Universite Rennes 2

Mathematiques - Travaux diriges

Arithmetique - suite

Algorithme d'Euclide

L'algorithme d'Euclide est un algorithme permettant de determiner le plus grand commun diviseur (PGCD)

de deux entiers sans conna^tre leur factorisation (leur decomposition en produit de facteurs premiers). Il

s'appuie sur deux proprietes. La premiere est la suivante : Propriete 1 :Soita,b,d,qetrdes entiers. On suppose quea=bq+r. Alorsddiviseaetbsi et seulement siddivisebetr.

Ainsi, en particulier, un nombre divise deux entiersaetbsi et seulement si il divise le reste de la division

Euclidienne deaparb. Il s'ensuit que la PGCD deaetb, qui fait partie de la liste des diviseurs deaetb

divise aussi le reste de la division Euclidienne deaparbdonc il fait partie de la liste des diviseurs dea,b

etr, reste de cette division. Par consequent, on a PGCD(a;b) = PGCD(b;r) avecrreste de la division euclidienne deaparb Propriete 2 :Il est par ailleurs clair que pour tout entiera,

PGCD(a;0) =a:

En eet, tout entier est un diviseur de 0 donc le plus grand diviseur commun entre 0 etalui-m^eme esta.

Voici une schematisation de l'algorithme d'Euclide :Applications 1.

Calculer PGCD( a;b) dans les cas suivants :

a= 230,b= 126 a= 390,b= 720 a= 112,b= 39 2.

Simplier si p ossibleles fractions suiv antes:

1045462

84238

195176

3.

Quels son tles diviseurs comm uns a390 et 525 ?

Nombres premiers - Nombres premiers entre eux

Nombre premier :Un nombre entier est dit premier s'il n'admet pas d'autre diviseur que 1 et lui-m^eme.

Noter que tous les nombres entiers ont la propriete d'^etre divisible par 1 et eux-m^emes. Les nombres premiers

sont sont qui n'admettent pas d'autre diviseur. Nombres premiers entre eux :Deux nombres sont dits premiers entre eux si leur plus grand diviseur

commun est 1. Noter cette fois que deux nombres ont toujours 1 comme diviseur commun. La particularite

des nombres premiers entre eux est qu'ils n'en ont pas d'autres (sinon leur PGCD serait superieur a 1).

Exercices

1. Soit nun entier positif. Montrer que le nombren2+ 2n3 n'est jamais un nombre premier. 2. Soit nun entier. On noten! (et on dit factoriellen) le nombre n! =n(n1)(n2):::21 Montrer, que quelque soit l'entiern, les nombres suivants ne peuvent pas ^etre premiers : n! + 2;n! + 3;:::;n! +n En deduire que pour tout entiern, il existen1 entiers consecutifs non premiers. 3. Les nom bressuiv antsson tils premiers en treeux ? a= 21 etb= 45a= 39 etb= 65 4.

On c herche amon trerque 3

1235 et 25 sont premiers entre eux.

Soitd= PGCD(31235;25). Pourquoidne peut ^etre egal qu'a 1, 5 ou 25? Est ce que 5 est un diviseur possible de 3123? de 31235?

Conclure.

Changements de base

1. Com bienv autle nom brequi s' ecrit10011 en base 2 ? 2. Com bienv autle nom brequi s' ecrit112 en base 3 ? 3. Ecrire le nom bre13 e nbase 2, p uisen base 3 puis en base 7.

Corrige

Algorithme d'Euclide

1.

Calculer PGCD( a;b) dans les cas suivants :

a= 230,b= 126

CorrigeOn deroule l'algorithme

PGCD(230;126) = PGCD(126;104) = PGCD(104;22) = PGCD(22;16) = PGCD(16;6) = PGCD(6;4) = 2 a= 390,b= 720

CorrigeOn deroule l'algorithme

PGCD(720;390) = PGCD(390;330) = PGCD(330;60) = PGCD(60;30) = 30 a= 112,b= 39

CorrigeOn deroule l'algorithme

PGCD(112;39) = PGCD(39;34) = PGCD(34;5) = PGCD(5;4) = 1 2.

Simplier si p ossibleles fractions suiv antes:

1045462

84238

195176

CorrigeDans chaque cas, cherchons le PGCD des nombres concernes. PGCD(1045;462) = PGCD(462;121) = PGCD(121;99) = PGCD(99;22) = 11 Ainsi

1045462

=9542 PGCD(238;84) = PGCD(84;70) = PGCD(70;14) = PGCD(14;0) = 14 Ainsi 84238
=617

PGCD(195;176) = PGCD(176;19) = 1

Ainsiquotesdbs_dbs47.pdfusesText_47

[PDF] montrer que n(n+1)(n+2) est divisible par 6

[PDF] Montrer que pour tout entier c : =1

[PDF] montrer que q est dénombrable

[PDF] montrer que racine de 3 est irrationnel

[PDF] montrer que racine de n est irrationnel

[PDF] montrer que se sont des rationnels

[PDF] montrer que si x appartient ? l'intervalle

[PDF] montrer que x appartient ? un intervalle

[PDF] montrer que xn 1 axn

[PDF] Montrer que y=

[PDF] MONTRER QUELQUE CHOSE SANS LE MONTRER POUR PEUT ÊTRE MONTRER TOUT AUTRE CHOSE

[PDF] Montrer registre tragique

[PDF] Montrer si le nombre A est un entier ou pas

[PDF] montrer une inégalité avec valeurs absolues

[PDF] montrer une relation d'ordre