Université Joseph Fourier MAT231 mat231 exo tex septembre

Joseph Fourier

Description

Niveau: Supérieur
Université Joseph Fourier – MAT231 – 2008-2009 mat231-exo-02-080902.tex (2 septembre 2008) Feuille d'exercices no 2 Note. Les exercices portant sur la mise en oeuvre algorithmique sont regroupés dans la Section Algorithmes à la fin de la feuille. Exercices Exercice 2.1 Donner le quotient et le reste de la division euclidienne de a par b, pour les couples (a, b) ci-après. Dans chacun des cas, écrire tous les calculs. 1. Division euclidienne de 55 par 13. 2. Division euclidienne de 647 par 27. 3. Division euclidienne de 573 par ?11. 4. Division euclidienne de ?735 par ?17. 5. Division euclidienne de ?947 par 23. Exercice 2.2 Une division euclidienne a = bq + r, 0 ≤ r < b, a pour dividende a = 557 et pour reste r = 85. Quelles sont les possibilités pour le diviseur (b) et pour le quotient (q) ? Exercice 2.3 Soient a, b ? N• et q le quotient de la division euclidienne de a par b. Quel est le quotient de la division euclidienne de abn ? 1 par bn+1, où n ? N•. Mise en oeuvre algorithmique de la division euclidienne : voir Exercices 2.45 et 2.46. Exercice 2.4 Écrire les tables d'addition et de multiplication en base 5.

• idéal de z


• n•


• système de numération par le symbole ?


• pgcd


• division euclidienne


• relation d'ordre dans n•

Sujets

• Fourier
• Division euclidienne

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 52
• Langue: Français

Extrait

Université Joseph Fourier – MAT231 – 2008-2009 mat231-exo-02-080902.tex (2 septembre 2008)

o Feuille d’exercicesn 2

Note.Les exercices portant sur la mise en oeuvre algorithmique sont regroupés dans la SectionAlgorithmesà la fin de la feuille.

Exercices

Exercice 2.1Donner le quotient et le reste de la division euclidienne deaparb, pour les couples(a, b)ci-après. Dans chacun des cas, écrire tous les calculs. 1. Division euclidienne de55par13. 2. Division euclidienne de647par27. 3. Division euclidienne de573par−11. 4. Division euclidienne de−735par−17. 5. Division euclidienne de−947par23.

Exercice 2.2Une division euclidiennea=bq+r,0≤r < b, a pour dividendea= 557et pour rester= 85. Quelles sont les possibilités pour le diviseur (b) et pour le quotient (q) ?

• Exercice 2.3Soienta, b∈Netqle quotient de la division euclidienne deaparb. Quel n n+1• est le quotient de la division euclidienne deab−1parb, oùn∈N.

Mise en oeuvre algorithmique de la division euclidienne :voir Exercices 2.45 et 2.46.

Exercice 2.4Écrire les tables d’addition et de multiplication en base5. Les utiliser pour calculer132 + 404et23×134en base5.

Exercice 2.5Montrer que si la base de numération est au moins égale à8, le nombre672 est divisible par32. Quel est alors le quotient ?

MAT 231

2008-2009

2

Exercice 2.6On se place dans un système de numération en basex≥2. On noteαle n plus grand entier qui s’écrit au moyen d’un seul chiffre. Comment s’écrit le nombrex−1 en basex?

2 2 Exercice 2.7Soitaentier supérieur ou égal à2. Développer(a+a+ 1)(a−a+ 1). En déduire que dans tout système de numération, le nombre10101est divisible par le nombre 111. Déterminer le quotient de ces deux nombres (on pourra représenter le nombre(a−1) du système de numération par le symboleβ).

FExercice 2.8On se donnea∈N, a≥2. On se donne également

p x:=x p a+∙ ∙ ∙+x 0 avecx p 6= 0,

et q y:=y q a+∙ ∙ ∙+y 0 avecy q 6= 0, deux nombresxetyécrits en basea(0≤x i < apouride0àpet0≤y j < apourjde0 àq). p p p 1. Montrer que l’on ax p a≤x≤x p a+a−1. 2. Montrer quep < qimplique quex < y. 3. Montrer quep=qetx p < y p impliquent quex < y. 4. Montrer quep=q,x p =y p , . . . , x r+1 =y r+1 etx r < y r pour un certainrtel que 0≤r < pimpliquent quex < y. 5. Déduire de ce qui précède l’unicité de l’écriture en basea.

Mise en oeuvre algorithmique de l’écriture en basea:voir Exercice 2.47.

a c Exercice 2.9Soient et deux fractions écrites sous forme réduite, aveca, c∈Z,b, d∈ b d • a c Netpgcd(a, b) = pgcd(c, d) = 1. On suppose que+∈Z. Que peut-on en déduire sur b d b, d?

√ Exercice 2.10Montrer que2n’est pas un nombre rationnel.

• Exercice 2.11On considèreNavec la relation|définie par

a|b

si et seulement si

adiviseb.

• 1. Montrer que la relation|est une relation d’ordre dansN. L’ordre ainsi obtenu est-il total ? • 2. On se donnea, b∈Net on posed:= pgcd(a, b). Indiquer par “Vrai” ou par “Faux” le statut des affirmations suivantes. Justifier votre réponse d’une ligne (argument ou contre-exemple). • (a) Le nombredest un minorant de{a, b}pour la relation|surN. • (b) Le nombredest le plus petit élément de{a, b}pour la relation|surN.

MAT 231

2008-2009

3

• (c) Le nombredest le plus grand des minorants de{a, b}pour la relation|surN.

• Exercice 2.12Soienta, b∈N. Combien y a-t-il d’entiers divisibles parbdans l’ensemble {ka|1≤k≤b}.

• Exercice 2.13Déterminer tous les couples d’entiers(a, b)∈Ndont la sommea+bvaut 360et dont lepgcdvaut18.

Exercice 2.14On se donne deux entiersa, b, non nuls et premiers entre 2 2 lespgcdde(a+b, a),(a+b, b)et(a+b, ab). Les nombresa+beta+b premiers entre eux ?

eux. Déterminer sont-ils toujours

FExercice 2.15Soienta, bdeux entiers non nuls, premiers entre eux. 1. On suppose quea > b. Montrer quepgcd(a+b, a−b)vaut1ou2. Préciser les cas où lepgcdvaut1, respectivement2. 2. On suppose quep, q, r, svérifientps−qr= 1. Calculer lepgcddepa+qbetra+sb.

Exercice 2.16Soienta, bdeux entiers non nuls, premiers entre eux. 1. Calculer lepgcddes couples(a, ab+ 1)et(a, ab+ 2). •n m 2. Sim, n∈N, calculer lepgcddeaetb.

• FExercice 2.17Soientm≥n∈N. Soitrle reste de la division euclidienne dempar n. 1. Comparer lespgcdpgcd(m, n)etpgcd(n, r). m n r 2. NotonsΔlepgcddea−1et dea−1. Montrer queΔdivisea−1. [IIndication : y+z y z y Pourx, y, zdes entiers, montrer quex−1 =x(x−1) +x−1.] 3. DéterminerΔ.

Exercice 2.18Montrer que l’on a l’égalitépgcd(a,pgcd(b, c)) = pgcd(pgcd(a, b), c)(asso- ciativité dupgcd).

Mise en oeuvre algorithmique du calcul du pgcd :voir Exercice 2.48.

Exercice 2.19Soienta, bdeux entiers non nuls. On désigne pard:= pgcd(a, b)et par 0 0 0 m:= ppcm(a, b)respectivement leurpgcdet leurppcm. On définita , bpara=daet 0 0 0 b=db. Montrer quem=da bet que

[ICours.]

ab= pgcd(a, b)×ppcm(a, b).

MAT 231

2008-2009

4

Exercice 2.20Montrer que l’on a l’égalitéppcm(a,ppcm(b, c)) = ppcm(ppcm(a, b), c)(as- sociativité duppcm).

Exercice 2.21Utiliser la décomposition en facteurs premiers pour déterminer lepgcdet leppcmde deux nombresaetb.

Exercice 2.22Soitnun entier supérieur ou égal à2. On posem:=n! + 1. Les entiers m+ 1, m+ 2, . . . , m+n−1? En déduire une liste depeuvent-ils tre premiers 1000entiers consécutifs, tous non premiers.

• Exercice 2.23Montrer que pour tout entierk∈N, et pour tout entierx≥2, l’entier k• x−1divise l’entierx−1. Soit un entiern∈N. n 1. Montrer que si2−1est premier, alorsnest premier. n 2. Montrer que si12 + est premier, alorsnest une puissance de2. 3. Tester la réciproque de chacune des deux assertions avecmapleouxcas.

Exercice 2.24Soitpun nombre premier. Résoudre, dansNl’équation

2 2 x−y=p.

Mise en oeuvre algorithmique de la décomposition en facteurs premiers :voir Exercices 2.49 et 2.50.

Exercice 2.25Soienta, b∈Z. Montrer que l’ensembleaZest un idéal deZ. Montrer que l’ensembleaZ+bZest un idéal deZ.

FExercice 2.26Soita∈N. On noteaZl’ensemble des élémentsx∈Zde la forme • x=ayavecy∈Z. Les éléments deaZsont appelés les multiples dea. Soienta, b∈N. On appelleppcm(plus petit commun multiple) deaetble plus petit entier strictement positif qui soit un multiple à la fois deaet deb. • 1. Montrer queaZ∩bZ∩Nest non vide et en déduire l’existence duppcm. 0 0 0 2. Sidest lepgcddeaetb, on posea:=daetb:=db. Notonsm:=a b. 0 (a) Montrer quem=abet en déduire quemest un multiple commun àaetb. (b) Un multiple demest-il un multiple commun àaetb? (c) Soitµun multiple commun àaetb. Montrer queµest un multiple dem. En déduire quemest leppcmdeaetbet vérifier queab=md. • 3. Montrer que l’ensembleaZ∩bZest un idéal deZ. en déduire qu’il existem∈Ntel queaZ∩bZ=mZ.Vérifier quemest leppcmdeaetb. 4. Dans le cadre de la question précédente, montrer queab=md, oùdest lepgcddea etb.

MAT 231

2008-2009

5

FExercice 2.27Un groupe de17pirates a rassemblé un trésor dexpièces d’or (x≤500). À l’issue d’un partage équitable, il reste7pièces. Une bagarre s’ensuit, un mort. Nouveau partage équitable, il reste11pièces. Nouvelle bagarre, nouveau mort et nouveau partage. Les 15pirates restant ont le mme nombre de pièces. Déterminer la taille du trésor.

Exercice 2.28Montrer que le théorème de Gauss découle du Théorème de Bézout.

Exercice 2.29Montrer, par exemple pour le couplea:= 876etb:= d’Euclide permet de déterminer un couple(u, v)vérifiant le théorème Mme question pour les couples(756,330),(120,35),(1344,231).

543, que l’algorithme de Bézout généralisé.

Exercice 2.30Détermineru 0 etv 0 tels que2u 0 + 3v 0 = 1. En déduire tous les couples (u, v)vérifiant la relation2u+ 3v= 1. Résoudre le système

x x

≡ ≡

1modulo2 2modulo3

Exercice 2.31On se place dansZ. 1. L’équation273x+ 33y= 5? Dans l’affirmative, donner l’en-a-t-elle des solutions semble des solutions. 2. L’équation273u+ 33v= 6? Dans l’affirmative, donner l’en-a-t-elle des solutions semble des solutions. On donnera tous les calculs.

Mise en oeuvre algorithmique de la division étendue (théorème de Bézout) :voir Exercice 2.51.

• Exercice 2.32Montrer que la congruence modulon∈Zest une relation d’équivalence dansZ, compatible avec les opérations deZ. [ICours.]

42 Exercice 2.33Montrer que9518−4est un multiple de5.

Exercice 2.34Écrire les tables d’addition et de multiplication dansZ/Z 3 . Soitxun entier 2 non nul. Le reste de la division euclidienne dexpar3peut-il tre égal à2?

Exercice 2.35On considère la suite{u n }d’entiers naturels définie par

u 0 u n+1

= =

14 5u n −6pour tout entier natureln

MAT 231

2008-2009

6

1. Calculeru 1 , u 2 etu 3 . 2. Montrer que, pour tout entier natureln,u n+2 ≡u n modulo4. En déduire que pour tout entier naturelk,u 2k ≡2modulo4etu 2k+1 ≡0modulo4. n+2 3. Montrer par récurrence que, pour tout entier naturel,2u n = 5 + 3. En déduire que, pour tout entier naturel n,2u n ≡28modulo100. 4. Déterminer les deux derniers chiffres de l’écriture décimale deu n suivant les valeurs den. 5. Montrer que lepgcdde deux termes consécutifs de la suite{u n }est constant et préciser sa valeur.

Exercice 2.36Donner un critère de divisibilité par7en base11. Le nombrendont la représentation en base11est10934est-il divisible par7? Le nombrendont la représentation en base10est10934est-il divisible par7?

2 2 Exercice 2.37Montrer que l’équation3x+ 2 =yn’a pas de solution dansZ.

216 Exercice 2.38Déterminer le reste de la division euclidienne de2792par5.

Exercice 2.39Démontrer que le carré de tout entier naturel est de la forme3nou3n+ 1, pour un certainn∈N.

Exercice 2.40Résoudre, ¯ ¯ 1. dansZ/7Z: 5×x¯ = 3, ¯ ¯ 2. dansZ/10Z: 3×x¯ = 5, ¯ ¯ 3. dansZ/6Z: 3×x¯ = 3.

1137 Exercice 2.41Donner les restes de la division euclidienne de2par17et par13; celui 359 de la division euclidienne de247par7.

Exercice 2.42Résoudre, dansZ,

a a

≡ ≡

5 2

(13), (17).

1137 En déduire le reste de la division euclidienne de2par221.

MAT 231

2008-2009

7

FExercice 2.43Cet exercice se compose de trois parties. 2 2 Partie ASoitnun entier naturel, impair et non premier. On suppose quen=a−boù a, bsont deux entiers naturels. 1. Montrer queaetbn’ont pas la mme parité. 2. Montrer quenpeut s’écrire comme produit de deux entiers naturelspetq. 3. Quelle est la parité depet deq? Partie BOn admet que250507n’est pas premier. On se propose de chercher les couples d’entiers naturels(a, b)vérifiant la relation 2 2 (E)a−250507 =b . 1. Soitxun entier naturel. 2 (a) Donner dans un tableau les restes possibles dexmodulo9, puis ceux dex modulo9. 2 2 (b) Sachant quea−250507 =b, déterminer les restes possibles modulo9de 2 2 a−250507. En déduire les restes possibles deamodulo9. (c) Montrer que les restes possibles deamodulo9sont1et8. 2. Justifier que si le couple(a, b)vérifie(E), alorsa≥501. Montrer qu’il n’existe pas de solution de(E)du type(501, b). 3. On suppose que le couple(a, b)vérifie(E). (a) Montrer queaest congru à503ou à505modulo9. (b) Déterminer le plus petit entier naturelktel que le couple(505 + 9k, b)soit solution de(E), puis donner le couple solution correspondant.

Exercice 2.44 dans l’ensemble

• • On se donnem∈N,a∈Zetb∈Z. Le but de l’exercice est d’étudier, Z, l’équation

(2.1)ax≡b(modm). 1. Dans cette question, on suppose quepgcd(a, m) = 1. (a) Montrer qu’il existeu∈Ztel queau≡1 (modm). (b) Montrer que l’équation (2.1) est équivalente à l’équation (2.2)x≡ub(modm).

(c) Donner toutes les solutions de l’équation (2.1) dansZ. 2. Dans cette question, on suppose quepgcd(a, m) =d >1. On posea=dαetm=dµ. (a) Montrer queaµ≡0 (modm). (b) Montrer qu’une condition nécessaire pour que l’équation (2.1) ait au moins une solution dansZest queddiviseb. (c) Dans cette question, on suppose queddivisebet on poseb=dβ. i. Montrer que l’équation (2.1) équivaut à l’équation (2.3)αx≡β(modµ).

ii. Décrire, si elle en a, les solutions de l’équation (2.1) dansZ. iii. Application : déterminer l’ensemble des solutions de l’équation 6x≡10)4 (mod

dans l’ensembleZ.

MAT 231

2008-2009

Algorithmes

8

Les exercices qui suivent concernent des algorithmes de mise en oeuvre de calculs arithmé- tiques (division euclidienne,pgcd,etc). Il s’agit de faire des algorithmes exacts (calculs exacts et non calculs approchés) et les plusefficacespossibles (minimiser le temps d’exé- cution, donc le nombre d’opérations). Les algorithmes pourront comporter des opérations arithmétiques (additionet soustraction,multiplication,division exacte) et des contrôles (tant que,. . alorssi . ,etc). On sera amené à compter le nombre d’opérations effectuées dans l’algo- rithme. Pour simplifier, on ne comptera ni le nombre de contrôles, ni les appels de variables. Les algorithmes seront décrit en langagehumain, puis codés pour (mapleou)xcasen vue des TP sur machine.

ℵExercice 2.45 (Algorithme de division euclidienne)Soienta, b∈N, tels quea≥ b≥1. Le but de l’exercice est d’écrire un algorithme ayant en entréeaetb, et en sortie le quotientqet le resterde la division euclidienne deaparb. On utilisera dans cet exercice uniquement des instructions de contrôle et l’addition. On définit les suites{r k } k≥0 et{q k } k≥0 par   •r 0 :=aetq 0 := 0, •pourk≥0et tant quer k ≥b,  r k+1 :=r k −betq k+1 :=q k + 1.

1. Montrer que les suites s’arrtent à partir d’un certain indicenet quer n =r, le reste de la division euclidienne deaparbet queq n =q, le quotient de cette division. 2. Écrire un algorithmemapleouxcascorrespondant aux suites précédentes. [IVoir TP.] 3. On suppose quebest fixé et queaest grand devantb. Déterminer, en fonction dea, l’ordre de grandeur du nombre d’opérations nécessaires pour calculer le quotient et le reste de la division euclidienne deaparb.

ℵExercice 2.46 (Algorithme de division euclidienne binaire)Soienta, b∈N, tels quea≥b≥1. Le but de l’exercice est d’écrire un algorithme de division euclidienne (en entrée les nombresaetb; en sortie le quotientqet le resterde la division euclidienne de aparb) plus efficace de l’algorithme de l’Exercice 2.45. Plus précisément, on cherche le quotientqsous forme binaire,

N−1N−2 q+= 2 α N−2 2 +∙ ∙ ∙+α 1 2 +α 0 ,

avecα j ∈ {0,1}. On utilisera uniquement des instructions de contrôle, l’addition, la multipli- cation et la division exacte (cf.Exercice 2.45, on pourra également réfléchir à un algorithme sans division). n−1 1. Montrer que le nombreNest le plus grand entierntel que2b≤a. En déduire un algorithme pour déterminerN. N−1N−2 2. Montrer queα N−2 = 1si et seulement sia−2b≥2b. On suppose que l’on a  N−1 déterminéα N−2 , . . . , α p . Montrer queα p−1 = 1si et seulement sia−2 +∙ ∙ ∙+  p p−1 α p 2b≥2b. 3. Déduire de la question précédente un algorithme permettant de calculerα j et de ranger α j dans la caseA[j+ 1]d’un tableauA[1]. . ,, . A[N]. 4. On suppose queaest grand devantb. Donner un ordre de grandeur du nombre d’opé- rations nécessaires pour remplir le tableauA(calcul deNet des coefficientsα j ).