Arithmétique

Table des matières

1.Calculs effectifs 1

1.1.Équations de Bezout 1

1.2.Systèmes dans 1

1.3.Divers 2

1.4.Base n 3

2.Raisonnement modulo m 3

2.1.Avec des carrés parfaits 3

2.2.Divers 4

3.Exos divers 4

3.0.1.Nombres de Fermat 4

3.0.2.Nombres de Mersenne 4

3.0.3.Période des développements décimaux 5

3.0.4.Entiers de Gauss 5

3.0.5.Écrire 999 comme différence de deux cubes 5

3.0.6.Divers 6

4.Théorèmes 6

4.0.7.Montrer Gauss à partir de Bezout. 6

4.0.8.Fermat 6

4.0.9.Théorème de Wilson 7

4.0.10.Un théorème d'Euclide sur les nombres parfaits 7

4.0.11.Il existe une infinité de premiers p de la forme p=4k+1. 7

1.Calculs effectifs

1.1.Équations de Bezout

Résoudre :

  1. 95x+71y=46 ;

    Réponse : { x=67-71k y=-89+95k. .

  2. 20x-53y=3 ;

    Réponse : { x=24+53k y=9+20k. .

  3. 12x+15y+20z=7 ;

    Réponse : { x=-49+20k-5m y=49-20k+4m z=-7+3k. .

  4. Trouver les coefficients de Bezout de 594 et 210.

    Voir à construire exercices numériques de ce genre avec xxx.dcode.fr.

    On trouve 210×17-594×6=6.

1.2.Systèmes dans

Résoudre :

  1. { x+y=56 xy=105. .

    Réponse 1 : on pose { d=xy m=xy . alors { d|105=3×5×7 d|56=23×7 .donc d{1;7}.

    On vérifie que

    {x,y}={21,35}
    fonctionne.

    Réponse 2 : on divise tout par 7 et on résoud { x'+y'=8 x'y'=15, .même raisonnement on aboutit à {x',y'}={3,5}.

  2. { xy=x-y xy=72. .

    Réponse : on pose (x,y)=d×(x',y') avec d=xy alors le système s'écrit :

    { 1=x'-y' x'y'=72d, .

    et donc y' et y'+1 sont diviseurs de 72 et donc y'{1,2,3,8}.

    S={{36,72},{24,36},{18,24},{8,9}} .

1.3.Divers

  1. Résoudre :

    { x+y = 56 xy = 105. .

    Réponse : on pose d=xy alors d|56105=7 :

  2. Trouver les (x,y) entiers tels que :

    k=1xk!=y2.

    Indication : Supposer k5 et raisonner sur le chiffre des unités du Σ.

    Réponse : 1!+2!+3!+4!=3(10) et si k5 alors k!=0(10) donc pas de solution pour x4.

    On examine alors les cas x=1,2,3 et on trouve :

  3. Résoudre dans 2 l'équation 3x3+xy+4y3=349.

    Réponse :

    déjà x3116 donc x4 ;

    de même y387 donc y4 ;

    si y=0 alors x3 ;

    selon les valeurs de y=1,2,3,4 on va aboutir à une équation en x sur laquelle on va essayer x=1,2,3,4 et seule la dernière va donner une solution qui fonctionne :

    y=13x3+x=345
    y=23x3+2x=317
    y=33x3+3x=241

    et pour y=4 on a 3x3+4x=93 avec x=3 qui marche donc (x,y)=(3,4) .

  4. Touver les entiers multiples de 30 possédant 12 diviseurs.

    Réponse : ce sont les n=2α3β5γ×7δ×11ε avec α,β,γ1, on trouve vite que δ=ε==0 et l'on a (α+1)(β+1)(γ+1)=12 d'où n{60,90,150}.

  5. n2 possède trois fois plus de diviseurs que n, déterminer n :

    1. en supposant que n n'admet que 2 et 3 comme facteurs premiers

    2. étudier les autres cas… à finir

  6. a,b des entiers de produit 11340 et possédant six diviseurs communs. Trouver a et b.

    Réponse : on a 11340=22×34×5×7 donc ab=18 donc {a,b}={18×5,18×7}.

1.4.Base n

  1. On pose un=10012 (n occurences du chiffre 0). Calculer en base 2 l'expression de :

    1. (un)2

      Réponse : (un)2=22n+2+2n+2+1=100 n-1 zéros 100 n+1 zéros 12.

    2. (un)3

      Réponse : (un)3=100 n-1 zéros 100 n-1 zéros 100 n-1 zéros 12.

    3. (un)4 (on supposera n>1).

      Réponse : (un)4=24n+4+23n+5+22n+5+1=100 n-2 zéros 100 n-1 zéros 11100 2n+4 zéros 1

    4. (un)8 (on supposera n4).

      Réponse : le n4 sert à assurer que les coef sont bien dans l'ordre strictement croissant.

      Sauf erreur !…

      (un)4=28n+8+27n+10+26n+10+26n+9+26n+8+25n+10+24n+8+24n+6+24n+5+23n+8+1 donc (un)4=100 n-3 zéros 100 n zéros 11100 n-3 zéros 100 n-3 zéros 101100 n-4 zéros 100 3n+6 zéros

2.Raisonnement modulo m

2.1.Avec des carrés parfaits

  1. Chercher les entiers a,b tels que k=1ak!=b2.

    Réponse : on raisonne modulo 5 ou modulo 10.

    Exemple modulo 5 :

    a 1!++a!
    1 1
    2 3
    3 4
    4 3
    4 3
    et
    b b2
    1 1
    2 4
    3 4
    4 1
    0 0
    donc les solutions sont à chercher parmi a{1;3} .

    Le cas a=1 donne (a,b)=(1,1) comme réponse possible.

    Le cas a=3 donne a=b=3 d'où :

    S={(1,1);(3,3)} .

  2. La somme de trois carrés parfaits ne peut pas être de la forme 7+8n.

    Réponse : modulo 8 on a :

    n 0 1 -1 2 -2 3 -3 4
    n2 0 1 1 4 4 1 1 0
    .

    On veut que la somme de trois entiers de la ligne du bas fasse 7-1 modulo 8, c'est impossible.

  3. La somme de cinq carrés parfaits consécutifs ne peut elle-même être un carré parfait.

    Réponse : (n-2)2+(n-1)2+n2+(n+1)2+(n+2)2=5(n2+2), il s'agit de voir si n2+2 peut déjà avoir un facteur 5, pour cela on raisonne modulo 5 :

    n(mod5) 0 1 2 3 4
    n2+2(mod5) 2 3 -1 2 3
    ,

    on voit que n2+2 n'est jamais multiple de 5 donc 5(n2+2) ne peut être un carré parfait.

2.2.Divers

  1. Si p et 8p2+1 sont premiers, alors 8p2-1 aussi.

    Réponse : on raisonne modulo 3 :

  2. Montrer que, modulo 7, la suite un=42n+22n+1 est constante.

    Réponse : il est facile de montrer par récurrence que modulo 7, on a { 42n=(4,2,4,2) 22n=(2,4,2,4) ..

  3. Division d'une congruence

    Si kxky[n], peut-on affirmer que xy[n] ?

    Réponse : on écrit : c/kx-ky=nc. À partir de là :

3.Exos divers

3.0.1.Nombres de Fermat

On pose Fn=22n+1, montrer que si np alors FnFp=1.

Indication : exprimer Fn+q en fonction de Fn.

Réponse : Fn+q=(Fn-1)2q+1=kFn+2 par Newton, donc 2|Fn+qFn, et vu que les Fn sont tous impairs, c'est gagné.

3.0.2.Nombres de Mersenne

  1. On pose pour n0 : Mn=2n-1. Montrer que si d|n alors 2d-1|Mn, en déduire que Mn premier n premier, la réciproque est-elle vraie ?

    Si n=dk alors Mn=(2d)k-1=(2d-1)(1+2d++(2d)k-1). La réciproque n'est pas vraie (M11 n'est pas premier).

  2. On pose a,n2, montrer que an-1 premier a=2 et n premier.

    Évident car on a toujours an-1=(a-1)(1+a++an-1).

3.0.3.Période des développements décimaux

Soit x avec x=pq et p,q premiers entre eux.

  1. Montrer l'équivalence entre :

    1. x admet un développement décimal de période n ;

    2. q|10n-1.

  2. En déduire la période de développement décimal de p7, où p est un entier premier avec 7.

Réponse : On a équivalence entre :

  1. x admet un développement décimal (de période n) ;

  2. 10n×x-x=x(10n-1) est un nombre entier (à n chiffres en comptant les éventuels 0) ;

  3. kq=p(10n-1)k (et possède n chiffres) ;

  4. q|10n-1.

Dans le sens ab,

Posons k=, ainsi k est un entier (à n chiffres).

Donc et par Gauss on a q|10n-1.

On trouve :

n facteurs premiers de 10^n-1 autres que 3 1 - 2 11 3 37 4 11,101 5 41,271 6 7,11,13,37

3.0.4.Entiers de Gauss

On pose (1+2)n=an+bn2avecan,bn. Montrer que anbn=1.

Cela reste-t-il vrai en remplaçant 2 par n avec n3 ?

Réponses possibles :

Cela ne marche pas en remplaçant 2 par n par exemple.

Ainsi :

3.0.5.Écrire 999 comme différence de deux cubes

De quelles manières 999 peut-il s'écrire comme différence de deux cubes ?

Réponse : On résoud donc a3-b3=999. Or on sait que a3-b3=(a-b)(a2+ab+b2).

On écrit les diviseurs de 999 en remarquant que 999=33×27. On obtient ainsi l'ensemble

D={1;3;9;27;37;111;333;999}

Ainsi d=a-b est un élément de D. Exprimons e=a2+ab+b2 en fonction de d.

On a alors d×e=999 et :

e = a^2+a*b+b^2 = (b+d)2+b(b+d)+b2 = 3b2+3bd+d2.

On cherche les solutions entières de l'équation en b suivante :

3b2+3d×b+(d2-e)=0.

Il faut alors que Δ=9d2-4×3(d2-e)=12e-3d2 soit un carré parfait.

On regarde donc, parmi tous les produits d×e=999, ceux tels que 12e-3d2 soit un carré parfait.

Les seuls qui conviennent sont :

(d=3;e=333) qui donne Δ=632 puis b=9

(d=9;e=111) qui donne Δ=332 puis b=1

Conclusion : 999=10^3-1=12^3-9^3

3.0.6.Divers

  1. On suppose p et 8p2+1 premier. Montrer que 8p2-1 premier aussi.

    Réponse : on raisonne modulo 3 :

  2. Soit un entier naturel n.

    1. Si n est premier avec tous les k<n, que dire de n ?

    2. Si (n-1)!(-1)[n] que dire de n ?

4.Théorèmes

4.0.7.Montrer Gauss à partir de Bezout.

Réponse : si { a|bc ab=1 . alors k,m,n/{ bc=ak ma+nb=1(E2) ., on multiplie E2 par c et on obtient :

mac+nak=c

d'où a|c.

4.0.8.Fermat

Soit p premier.

  1. Montrer que k{1;;p-1}, p|( p k )..

  2. Montrer que a, apa[p] par récurrence sur a.

  3. Montrer que a, on a : [paap-11[p]].

  4. Cas où p non premier

    a) Montrer que pour tout entier n, on a : 6|5n3+n..

    b) Montrer que cela revient à affirmer que n3 et n ont toujours la même congruence modulo 6. Le théorème de Fermat est donc parfois vrai pour des p non premiers. Vérifier pour p=4,8,9,10,12,14,15.

Réponses :

  1. Deux méthodes :

    p!=( p k )k!(n-k)! puis par Gauss p|( p k )

    k( p k )=p( p-1 k-1 ) et Gauss aussi.

  2. a=1 ok. Hérédité : (a+1)p=apa par hérédité+1+n=1p-1( p n )anmultiple de p d'après a.=a+1 (modulo p).

  3. On divise la congruence précédente par p.

  4. a) On raisonne modulo 2 puis modulo 3 ou directement modulo 6.

4.0.9.Théorème de Wilson

Montrer que si n2, on a toujours :

(n-1)!=-1(n)n premier.

Réponse : on part de l'hypothèse :

k/(n-1)!+kn=-1 n(n-1)!=1 n premier avec tous les mn-1 n premier.

4.0.10.Un théorème d'Euclide sur les nombres parfaits

Si 2n+1-1 est premier, alors 2n(2n+1-1) est parfait.

Réponse : il suffit de lister ses diviseurs qui sont les {2k} et les {2k×(2n+1-1)} et d'en faire la somme. On trouve par ce procédé les nombres parfaits 6,28,16×31,64×127.

4.0.11.Il existe une infinité de premiers p de la forme p=4k+1.

  1. Soit p3 premier diviseur de n2+1n. Montrer que p1[4].

  2. Soit n, montrer que les diviseurs de (n!)2+1 sont supérieurs à n.

  3. Conclure.

Réponse :

  1. k/kp-n2=1 donc :

    • par Bezout pn=1 donc par Fermat np-11[p] ;

    • d'autre part n2-1[p] ;

    • on a envie de mêler ces deux égalités, pour cela on élève la seconde à la puissance p-12. On obtient : (-1)p-121[p] donc p-12 pair donc p1[4].

  2. Si (n!)2+1=μd alors, par Bezout, μ est premier avec (n!)2 donc avec n! donc μ>n.

  3. Conclusion : soit n aussi grand que l'on veut, soit μ un diviseur premier de (n!)2+1 alors μ>n et μ1[4].