Retour à la page personnelle de Bernard Parisse.

# Chapitre 3 Arithmétique en terminale scientifique

## 3.1 Énoncé sur la partie entière

Montrer que la partie entière de a=(3+√5)n est un entier impair quelquesoit l’entier n dans ℕ.

### 3.1.1 Cherchons avec `Xcas`

On peut faire des essais dans le tableur.
Dans A0 on met 1
Dans A1 on met =A0*(3+sqrt(5))
Dans B0 on met =floor(A0)
Dans B1 on met =floor(B1)
Puis on remplit vers le bas.
Dans cet exercice il faut penser à associer à (3+√5)n sa quantité conjuguée (3−√5)n.
Dans C0 on met 1
Dans C1 on met =C0*(3-sqrt(5))
Dans D0 on met =floor(A0+C0)
Dans D1 on met =C0*(3-sqrt(5))
Puis on remplit vers le bas.

### 3.1.2 La démonstration

On remarque que :
b=(3+√5)n+(3−√5)n est un entier pair (d’après la formule du binôme) et que 0<(3−√5)n<1.
On a donc a<b<a+1, ou encore b−1<a<b avec b un entier pair.
Cela prouve que la partie entière de a=(3+√5)n est b−1 qui est un entier impair.

## 3.2 Énoncés sur le nombre de diviseurs d’un entier

### 3.2.1 L’énoncé 1

Quel est, parmi les entiers naturels de 1 à 2005, celui qui admet le plus de diviseurs ? Quel est ce nombre de diviseurs ?

### 3.2.2 Réponse avec `Xcas`

On tape :
`2*3*5*7`
On obtient :
`210`
On tape :
`2*3*5*7*11`
On obtient :
`2310`
Cela nous dit que le nombre est de la forme :
2a*3b*5c*7d avec a ≥ b ≥ c ≥ d ≥ 0
et alors son nombre de diviseurs est :
(a+1)(b+1)(c+1)(d+1)
On peut maintenant faire une recherche systématique :
Il semble qu’il faut supposer que d ≠ 0 car avec - b=0,c=0, d=0 on ne peut avoir que 210 qui n’a que 11 diviseurs,
- c=0,d=0 (a+1)(b+1)
vaut 20 pour a=9 et b=1 (29*3=1536)
vaut 28 pour a=6 et b=3 (26*33=1728)
- d=0 (a+1)(b+1)(c+1)
vaut 32 pour a=7, b=1 et c=1 (27*3*5=1920)
vaut 36 pour a=5, b=2 et c=1 (25*32*5=1444)
- si d ≠ 0
On tape :
`210*6`
On obtient :
`1260`
et 1260 admet 3*3*2*2=36 diviseurs ou on tape :
`size(idivis(1260))`
On obtient :
`36`
On tape :
`210*8`
On obtient :
`1680`
et 1680 admet 5*2*2*2=40 diviseurs ou on tape :
`size(idivis(1680))`
On obtient :
`40`
On fait une recherche systématique :
210=1024 a 11 diviseurs,
29*3=1536 a 20 diviseurs,
27*32=1116 a 24 diviseurs,
26*33=1728 a 28 diviseurs,
24*34=1296 a 25 diviseurs,
27*3*5=1920 a 32 diviseurs,
25*32*5=1440 a 24 diviseurs,
24*3*5*7=1680 a 40 diviseurs.

### 3.2.3 L’énoncé 2

1/ Trouver le plus petit nombre entier n qui admet exactement 50 diviseurs.
2/ Existe-t-il un entier m qui soit inférieur à n et qui admette plus de 50 diviseurs ?

### 3.2.4 Réponse avec `Xcas`

On sait que si n=ap*bq*cr le nombre de diviseurs de n est (p+1)(q+1)(r+1).
On a :
`50=1*50=2*25=10*5=2*5*5` 1/ On cherche le plus petit nombre entier qui admet exactement 50 diviseurs, donc les candidats sont :
249
224*3
29*34
24*34*5
C’est donc 6480=24*34*5
On tape :
`size(idivis(6480))`
On obtient :
`50`
2/ On doit avoir :
m<24*34*5 donc pour qu’il est plus que 50 diviseurs il faut que m soit de la forme m=2p*3q*5r*7s avec p<=4,q<4,r=1,s=1 et 4(p+1)(q+1)>50.
Essayons p=4,q=2, on a 4(p+1)(q+1)=60>50 et m=24*32*5*7=5040.
Donc m= répond à la question.

## 3.3 Énoncés sur l’identité de Bézout

### 3.3.1 L’énoncé 1

Quel est le plus petit nombre entier avec lequel il faut multiplier 49 pour obtenir un nombre se terminant par 999999999 (9 neufs) ?

Réponse niveau primaire
On peut faire une multiplication à trous :

49*.........=..999999999

On trouve :

49*693877551=33999999999

Réponse niveau collège
On a 9999999999=109−1 et le résultat de la multiplication doit être de la forme n*109+109−1 avec 0≤ n<49 (ou de la forme p*109−1) avec 0< p ≤ 49.
On utilise le tableur en cherchant n pour que : n*109+109−1 soit divisible par 49.
On utilisera les commandes `irem(a,b)` et `iquo(a,b)` qui renvoient respectivement le reste et le quotient de la division euclidienne de `a` par `b`.
Pour cela on met dans la première colonne les nombres de 0 à 48, puis dans la deuxième colonne les nombres n*109+109−1 pour n de 0 à 48. Dans la troisième colonne on calcule le reste de la division de la deuxième colonne par 49 et on trouve que pour n=33 ce reste est nul. Il reste à calculer `iquo(33*10```^```9+10```^```9-1,49)` et on trouve :

693877551

Mais cette méthode est très couteuse ! On peut aller un peu plus vite (surtout si on veut faire les calculs à la main) en remarquant que 10=3 mod7 et que 100=2 mod49 donc :
103=−1 mod7
106=1 mod7
109=−1 mod7
108=24=16 mod49
109=13 mod49
13*−7=7 mod49
On cherche a tel que a*109=49*k+1=7*p+1.
donc −a=1 mod7 et 13*a=1 mod49
Si a=48 on a 13*a=−13=36 mod49
Si a=41 on a 13*a=13*−1+13*−7=−13+7=−6 mod49
Si a=34 on a 13*a=13*−1+13*−7+13*−7=1 mod49
Donc 34*109=1 mod49
Il reste à calculer `iquo(34*10```^```9-1,49)` et on trouve :

693877551

Réponse niveau TS
On a : 999999999+1=109.
On cherche p pour avoir : p*49=a*109−1 c’est à dire 1=a*109−p*49.

Avec `Xcas` on tape :
`bezout_entiers(49,10```^```9)`
On obtient :
`[306122449,-15,1]`
Donc :
49*306122449−15*109=1 et puisque 49*109−49*109=0, on a :
49*(109−306122449)+(15−49)*109=−1.
Puisque 109−306122449=693877551 et (49−15)=34, on a :

49*693877551=34*109−1=33999999999

Pour faire les calculs à la main on écrit :
109=13 mod49
donc on écrit les 2 premières équations :

0*13+1*49=49

1*13+0*49=13

puisque 49=3*13+10 on soustrait 3 fois l’équation 2 à l’équation 1 et on obtient l’équation 3 :

−3*13+1*49=10

puisque 13=1*10+3 on soustrait l’équation 3 à l’équation 2 et on obtient l’équation 4 :

4*13−1*49=3

puisque 10=3*3+1 on soustrait 3 fois l’équation 4 à l’équation 3 et on obtient l’idendité de Bézout :

−15*13+4*49=1

On a −15=34 mod49 et 109=13 mod49 donc 34*109−1 est divisible par 49.
Il reste à calculer `iquo(34*10```^```9-1,49)` et on trouve :

693877551

### 3.3.2 L’énoncé 2

Résoudre en nombres entiers :

13x+5y=1

5x+13y=6

Avec `Xcas` on tape :
`bezout_entiers(13,5)`
On obtient :
`[2,-5,1]`
Donc 2*13−5*5=1.
et puisque k*13*5−k*13*5=0, on a : 13*(2+5k)−(5+13k)*5=1.
13x+5y=1 a donc comme solutions x=2+5k,y=−5−13k avec k dans ℤ.
En multipliant l’égalité 13*(2+5k)−(5+13k)*5=1 par 6 on a :
13*(12+30k)−(30+78k)*5=6
5x+13y=6 a donc comme solutions x=−30−78k,y=12+30k avec k dans ℤ.

## 3.4 Énoncés sur des nombres de ℤ/pℤ

### 3.4.1 L’énoncé 1

Trouver les 2 derniers chiffres de 1996919969.

Ici, on est sûr que le dernier chiffre est 9, puisque 19969 est un nombre impair.
On peut utiliser le tableur pour chercher les 2 derniers chiffres de 69n.
Cela nous montre que 6910k=1 et que 6910k−1=29.
Donc les 2 derniers chiffres de 1996919969 sont 29.

On peut aussi taper directement pour vérifier :
`irem(19969```^```19969,100)`

### 3.4.2 L’énoncé 2

Trouver les 2 derniers chiffres de 1999619996.

Ici, on est sûr que le dernier chiffre est 6.
On peut utiliser le tableur pour chercher les 2 derniers chiffres de 96n.
Cela nous montre que 965k+1=96.
Donc les 2 derniers chiffres de 1999619996 sont 96.

On peut aussi taper directement pour vérifier :
`irem(19996```^```19996,100)`

## 3.5 TP sur l’indicatrice d’Euler

### 3.5.1 L’énoncé

Bijection entre ℚ ∩ [0,1] et ℕ
On construit une bijection f entre les rationnels de [0,1] et ℕ, pour cela :

- on ordonne les rationnels de [0,1] de la façon suivante :

  0,1,

  1
  2

  ,

  1
  3

  ,

  2
  3

  ,

  1
  4

  ,

  2
  4

  ,

  3
  4

  , ...

  1
  n

  2
  n

  ...

  n−1
  n

  ,...

- on supprime les fractions non irréductibles et on obtient une suite L.

La fonction f attribue à un rationnel de [0,1] son rang dans la suite L, on a : f(0)=0, f(1)=1, f(1/2)=f(2/4)=2, f(1/3)=3..., f(3/4)=6,..., f(1/5)=7....

1. Déterminer le nombre d’éléments de L qui a comme dénominateur 23 (resp 24, 25...30), à l’aide de l’indicatrice d’Euler,
2. Déterminer f(1/7) puis f(1/30), f(13/30) et f(29/30),
3. Écrire un programme qui etant donné deux entiers a et b (a<b) renvoie la liste des entiers plus petit que a qui sont premiers avec b,
4. Écrire un programme qui définit la fonction f ayant pour variable une fraction r de [0,1],
5. Écrire un programme qui pour n>0 trace les points de coordonnées a/b,f(a/b) avec b ≤ n. Afficher les points de coordonnées a/b,f(a/b) avec b<=32
6. Amusez vous à tracer ces points avec une couleur qui varie selon la valeur a de a/b.....

### 3.5.2 Le corrigé avec `Xcas`

On utilise la fonction `euler` de `Xcas` qui est l’indicatrice d’Euler c’est à dire `euler(n)` renvoie le nombre d’entiers inférieur à `n` qui sont premiers avec `n` (`euler(n)=card({p<n,gcd(n,p)=1})`).

1. Le nombre d’éléments de L qui a comme dénominateur 23 est le nombre d’entiers inférieur à 23 qui sont premiers avec 23 c’est donc `euler(23)`.
   On tape :
   `euler([23,24,25,26,27,28,29,30])`
   On obtient :
   `[22,8,20,12,18,12,28,8]`
   On a :
   f(1/5) est `euler(1)+euler(2)+...+euler(4)+1` On vérifie, on sait que f(1/5)=7 et `sum(euler(n),n,1,4)+1` vaut bien 7.
   On a :
   f(1/7) est `euler(1)+euler(2)+...+euler(6)+1` donc on tape :
   `sum(euler(n),n,1,6)+1`
   On obtient f(1/7) :
   `13`
   On tape :
   `sum(euler(n),n,1,29)+1`
   On obtient f(1/30):
   `271`
   Pour avoir f(13/30), il faut avoir le cardinal des entiers p>1 qui sont premiers avec 30 et inférieurs ou égaux à 13. Les nombres premiers inférieurs ou égaux à 13 sont 2,3,5,7,11,13 et `ifactor(30)=2*3*5` Donc f(13/30)=f(1/30)+3=274.
   Puisque 29/30 est le plus grand élément de dénominateur 30, pour avoir f(29/30), on tape :
   `sum(euler(n),n,1,30)`
   On obtient f(29/30) :
   `278`
   On sait que `euler(30)=8` et les 8 entiers inférieurs ou égaux à 30 qui sont premiers avec 30 sont : `1,7,11,13,17,19,23,29`.
2. On peut aussi écrire un petit programme qui renvoie la liste des entiers plus petit que a et premier avec b :

         Lppapremb(a,b):={
           local L,k;
           L:=NULL;
           for (k:=1;k<=a;k:=k+1){
             if (gcd(k,b)==1) {
               L:=L,k;
             }
           }
           return [L];
         }:;

   On tape :
   `sum(euler(n),n,1,29)+size(Lppapremb(1,30))`
   On obtient `f(1/30)` :
   `271`
   On tape :
   `sum(euler(n),n,1,29)+size(Lppapremb(13,30))`
   On obtient `f(13/30)` :
   `274`
   On tape :
   `sum(euler(n),n,1,29)+size(Lppapremb(29,30))`
   On obtient `f(29/30)`:
   `278`
3. Pour avoir la valeur de f(a/b) il suffit connaitre la longueur s de la liste des entiers plus petit que a et premier avec b .
   On utilise les fonction `numer` (resp `denom`) qui renvoie le numerateur (resp dénominateur) de la fracton simplifiée.
   On tape :

         f(r):={
           local s,k,a,b;
           a:=numer(r);
           b:=denom(r);
           s:=0;
           for (k:=1;k<=a;k:=k+1){
             if (gcd(k,b)==1) {s:=s+1;}
           }
           return sum(euler(n),n,1,b-1)+s;
         }:;

   On tape :
   `f(1,30)`
   On obtient `f(1/30)` :
   `271`
   On tape :
   `f(13,30)`
   On obtient `f(13/30)` :
   `274`
   On tape :
   `f(29,30)`
   On obtient `f(29/30)` :
   `278`
   On tape :
   `f(31,32)`
   On obtient `f(31/32)`:
   `324`
   On tape :
   `f(39,40)`
   On obtient :
   `490`
4. Pour tracer les points de coordonnées a/b,f(a/b), on ne se sert pas de la fonction f mais on calcule sa valeur au fur et à mesure et on la met dans la variable `valf` : à chaque étape `valf` augmente de `1`.

         tracef(n):={
           local L,a,b,valf;
           L:=point(0),point(1);
           valf:=1;
           for (b:=2;b<=n;b:=b+1){
             for (a:=1;a<b;a:=a+1){
               if (gcd(a,b)==1) {
                 valf:=valf+1;
                 L:=L,point(evalf(a/b)+i*valf);
               }
             }
           }
           return affichage(L,rouge+point_point+
                              epaisseur_point_2);
         }:;

   On tape :
   `tracef(40)`
   On obtient :
   Remarque Si on tape

         tracer(n):={
           local L,a,b;
           L:=point(0),point(1);
           for (b:=2;b<n;b:=b+1){
             for (a:=1;a<b;a:=a+1){
               if (gcd(a,b)==1){L:=L,point(evalf(a/b)+i*f(a/b));}
             }
           }
           return affichage(L,rouge+point_point+
                              epaisseur_point_2);
         }:;

   Le temps de réponse est beaucoup plus long car le programme calcule à chaque ètape `f(a/b)` sans tenir compte des valeurs de `f` calculées auparavant. Le temps mis pour faire `tracer(100)` est de 160.02s alors que celui de `tracef(100)` est de 3.52s.
   On peut encore diminuer le temps de calcul en stockant par référence (avec `=<` au lieu de `:=`) les points dans la liste `L`. Pour cela il faut connaitre la longueur `s` de la liste `L` qui est `f((n-1)/n)`.
   On tape :

       tracerf(n):={
         local L,a,b,valf,s,j;
         s:=f((n-1)/n);
         L:=makelist(0,1,s);
         L[0]=<point(0);
         L[1]=<point(1);
         valf:=1;
         j:=2;
         for (b:=2;b<=n;b:=b+1){
             for (a:=1;a<b;a:=a+1){
               if (gcd(a,b)==1) {
                 valf:=valf+1;
                 L[j]=<point(evalf(a/b)+i*valf);
                 j:=j+1;
               }
             }
           }
           return affichage(L,rouge+point_point+
                              epaisseur_point_2);
         }:;

   On tape :
   `tracerf(100)`
   On obtient en 0.89s :
5. On met un peu de couleur ....
   On tape :

         tracerfc(n):={
           local L,a,b,valf,s,j;
           s:=f((n-1)/n);
           L:=makelist(0,1,s);
           L[0]=<point(0);
           L[1]=<point(1);L:=point(0),point(1);
           valf:=1;j:=2
           for (b:=2;b<=n;b:=b+1){
             for (a:=1;a<b;a:=a+1){
               if (gcd(a,b)==1) {
                 valf:=valf+1;
                 L[j]=<point(evalf(a/b)+i*valf,affichage=
                     irem(a,7)+point_point+epaisseur_point_2);
                 j:=j+1;
               }
             }
           }
           return L;
         }:;

   On tape :
   `tracerfc(100)`
   On obtient en 0.84s :
   On remarque que les points (1/(n+1),f(1/(n+1))) et les points ((n−1)/n,f((n−1)/n) semblent être sur des courbes symétriques par rapport à x=1/2, cela s’explique puisque f((n−1)/n)+1=f(1/(n+1)).

### 3.5.3 Prolongement du TP sur l’indicatrice d’Euler

Approximation d’un nuage de points La fonction f est la bijection entre ℚ ∩ [0,1] et ℕ qui a èté définie dans le TP précédent.

1. À l’aide du tableur tracer le nuage de points de coordonnèes : 1/n,f(1/n) où f est la fonction définie précédement. On rappelle que l’on a :

   f(

   1
   n

   )=1+

   n−1
   ∑
   k=1

   Φ(k) pour n∈ ℕ*

   où Φ est la fonction d’Euler.
2. On se demande si ces points sont sur une courbe identifiable. Dans le livre d’Hardy and Wright d’introduction à la théorie des nombres, il est dit que Φ(n) 3n2/π2 pour n grand. Vérifier ce résultat en utilisant une régression convenable.

### 3.5.4 Corrigé du prolongement du TP sur l’indicatrice d’Euler

1. On ouvre le tableur avec par exemple 100 lignes.
   - dans la colonne `A`, on met la suite des nombres entiers 1,2....,
   - dans la colonne `B`, on met l’inverse de ces nombres. Pour cela on met dans `B0` : `1` et dans `B1` : `=$B$0/A1`. Puis on copie cette formule vers le bas.
   - dans la colonne `C`, on met dans `C0` : `1`, dans `C1` : `=euler(A0)+1` et dans `C2` : `=euler(A0)+C1`. Puis on copie cette formule vers le bas.
   On sélectionne les 2 colonnes `B` et `C`, puis dans le menu `Maths->2-d stats` on choisit `nuage de points` la plage de cellule est alors : `B0:C99` et la cellule cible `D0` si on a coché `Graphe` et décoché `Paysage` dans la configuration du tableur on obtient
2. On modifie `B0` en `1.0` pour avoir des nombres approchés dans la colonne `B`. Puis on sélectionne les 2 colonnes `B` et `C`, puis dans le menu `Maths->Regressions` on choisit `Puissance` la plage de cellule est alors : `B40:C99` et la cellule cible `D1` (on a coché `Graphe` et décoché `Paysage` dans la configuration du tableur), puis on modifie `D1` en :
   `=power_regression_plot(matrix(50,2,(B50):(C99)),color=rouge)` et on obtient en rouge :
3. on met dans `D2` `=(M:=matrix(60,2,(B40):(C99)))`.
   Puis on tape : `=power_regression(M)`
   On obtient : `-2.01348683765,0.283029041082`
   On tape : `evalf(3/pi```^```2)`
   On obtient : `0.303963550927`

## 3.6 Un exercice sur les congruences et les restes chinois

### 3.6.1 L’énoncé

Trouver un nombre entier n vérifiant 4<n<N vérifiant :
n est divisible par 2
n−1 est divisible par 3
n−2 est divisible par 5
n−3 est divisible par 7
n−4 est divisible par 11

### 3.6.2 Solution avec `Xcas` et les restes chinois

On utilise la commande `ichinrem`.
On tape :
`ichinrem([0%2,1%3,2%5,3%7,4%11]))`
On obtient : `-788 % 2310`
On veut que 0<n<N donc :
n=(2310−788)+2310*k=1522+2310*k avec k≤ iquo((N−1522),2310) donc si N=10000 on tape :
`iquo((10000-1522),2310)`
On obtient :
`3`
On tape :
`(1522+2310*k)$(k=0..3)`
On obtient :
`1522,3832,6142,8452`

### 3.6.3 Solution avec `Xcas` et l’identité de Bézout

On utilise la commande `iabcuv` qui étant donné trois entiers `a,b,c` renvoie une liste de deux entiers relatifs `[u,v]` vérifiant `a*u+b*v=c`.
Remarque

- Si deux entiers relatifs u,v vérifie au+bv=c alors on a aussi :
  a(u+kb)+b(v−ka)=c pour tout k ∈ ℤ.
- `iabcuv` est une généralisation de l’identité de Bézout (commande `iegcd`). On a en effet : `iegcd(a,b)` renvoie une liste de trois entiers `[u,v,d]` vérifiant `a*u+b*v=d=gcd(a,b)` (où `gcd(a,b)` est le pgcd de `a` et `b`).
  Donc pour que `iabcuv` ait une solution il faut et il suffit que `c` soit un multiple du pgcd de `a` et `b`. Donc `iabcuv` a toujours une solution si `a` et `b` sont premiers entre eux.

On cherche n vérifiant :
n est un multiple de 2 et aussi un multiple de 3 plus 1.
Donc on a : n=2p=3q+1 avec p∈ ℤ et q∈ ℤ.
c’est à dire 2p−3q=1.
On tape : `iabcuv(2,3,1)`
On obtient : `[-1,1]`
Donc n=2*(−1+3k)=−2 % 6.
De plus n est un multiple de 5 plus 2.
Donc on a : n=5r+2=−2+6k avec r∈ ℤ et k∈ ℤ.
c’est à dire 6k−5r=4.
On tape : `iabcuv(6,5,4)`
On obtient : `[-1,2]`
Donc n=6*(−1+5k)−2=−8 % 30.
De plus n est un multiple de 7 plus 3.
Donc on a : n=7j+3=−8+30k avec j∈ ℤ et k∈ ℤ.
c’est à dire 30k−7j=11.
On tape : `iabcuv(30,7,11)`
On obtient : `[2,-7]`
Donc n=30*(2+7k)−8=52 % 210.
De plus n est un multiple de 11 plus 4.
Donc on a : n=11m+4=52+210k avec m∈ ℤ et k∈ ℤ.
c’est à dire 11m−210k=48.
On tape : `iabcuv(11,210,64)`
On obtient : `[-72,4]`
Donc n=11*(−72+210k)+4=−788 % 2310.
On tape : `(-788+k*2310)$ (k=1..4)`
On obtient : `1522,3832,6142,8452`

Retour à la page personnelle de Bernard Parisse.