Soit . Établir les divisibilités suivantes:
.
Pour , on désigne par le nombre de diviseurs positifs de et par leur produit. Quelle relation existe-t-il entre , et ?
Solution
En associant dans chaque diviseur avec celui qui lui est conjugué , on obtient un produit de termes égaux à . Ainsi,
Déterminer les tels que:
.
Résoudre dans les équations suivantes:
.
Solution
n’est pas solution. Pour ,
Ainsi,
n’est pas solution. Pour ,
Ainsi,
(Équations diophantiennes)
Déterminer les couples vérifiant:
.
Résoudre dans les équations suivantes:
Solution
On a
En détaillant les diviseurs de 6 possibles, on obtient
Pour ,
En détaillant les diviseurs de 25 possibles, on obtient
On a
et donc
En détaillant les diviseurs de 8 possibles et sachant
on obtient
Soit un ensemble de entiers distincts tous inférieurs ou égaux à .
Montrer qu’il existe deux éléments de tels que l’un divise l’autre.
Pour , on note le nombre de diviseurs positifs de et la somme de ceux-ci.
Coder une fonction qui donne et une autre qui donne .
Déterminer tel que .
Tracer et et conjecturer une inégalité.
Montrer .
Démontrer la conjecture de la question (c).
En déduire les points fixes de .
De même trouver les points fixes de .
On considère la série
Montrer que cette série converge et donner une valeur approchée de à près.
Solution
On parcourt les entiers allant de à et l’on cumule les diviseurs de .
def s(n): res = 0 for d in range(1, n+1): if n % d == 0: res += d return res def t(n): res = 0 for d in range(1, n+1): if n % d == 0: res += 1 return res
À l’aide d’une boucle while, on recherche convenable.
n = 2 while s(t(n)) != n: n += 1 print(n)
On obtient .
On représente les deux courbes
import matplotlib.pyplot as plt N = list(range(1, 21)) plt.plot(N, [s(t(n)) for n in N]) plt.plot(N, [2**(5/2)*n**(3/4) for n in N]) plt.show()
On observe .
Les diviseurs de vont par paires et l’un des deux entiers est assurément inférieur à . Il y a au plus paires avec . Il y a donc au plus diviseurs positifs de .
Il y a au plus diviseurs de tous inférieurs à donc
On en déduit
Pour ,
Il n’y a donc pas de points fixes à en dehors de
Il suffit de rechercher les solutions dans cet intervalle pour conclure.
n = 2 while n <= 1024: if s(t(n)) == n: print(n) n += 1
On obtient les valeurs , et .
On a
Cette fois-ci, les solutions figurent nécessairement dans . On obtient les valeurs , et .
On a
Par comparaison de séries à termes positifs, la série étudiée converge.
Le reste de rang de cette série vérifie
Pour vérifiant (par exemple ), une valeur décimale approchée de à près répond à la question.
def S(n): res = 0 for i in range(1, n+1): res += t(i)**2 / i**3 return res print(S(8000))
On obtient à près.
[<] Divisibilité[>] Calculs en congruence
Soient et , on note le quotient de la division euclidienne de par .
Déterminer pour tout , le quotient de la division euclidienne de par .
Solution
avec .
.
Or donc la relation ci-dessus est la division euclidienne de par .
Le quotient de celle-ci est donc .
(Développement factoriel d’un entier)
Montrer que pour tout , il existe et tels que
Vérifier l’unicité de cette écriture.
[<] Division euclidienne[>] PGCD et PPCM
Quel est le reste de la division euclidienne de par 7?
Solution
et donc .
donc .
Par suite, . Le reste cherché est 4.
Montrer que pour tout :
Solution
Pour on a donc .
.
.
.
or donc .
or donc .
Montrer que si est entier impair alors
Solution
On peut écrire et alors
Puisque l’un des facteurs de est pair, le produit est multiple de 8 et donc
Soient et deux entiers. Établir
Soient et . On suppose et premiers entre eux. Montrer
Solution
Si alors divise et divise a fortiori .
Si alors divise . Or et sont supposés premiers entre eux donc, en vertu du théorème de Gauss, divise .
Soient la somme des chiffres de , celle de et enfin celle de .
Que vaut ?
Solution
Posons , , donc .
Sachant , on a , puis . Or donc .
[<] Calculs en congruence[>] Nombres premiers entre eux
Calculer le pgcd des entiers et et déterminer un couple de coefficients entiers exprimant une relation de Bézout .
Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers et suivants:
.
Solution
et .
et
et
Soient . Montrer l’équivalence:
Solution
Supposons avec . et donc .
Supposons . On peut écrire avec .
Par l’égalité de Bézout, il existe tels que
et on a alors
avec et
(Coefficients de l’égalité de Bézout)
Soient et deux entiers non nuls de pgcd . Notre but est de déterminer tous les couples tels que .
Justifier l’existence d’un couple solution .
Exprimer à partir de tous les couples solutions.
Soient et des entiers. Établir
Résoudre dans les systèmes:
Solution
Soit solution. donc et avec premiers entre eux.
donc d’où
Les couples et sont à éliminer car 2 et 6 ne sont pas premiers entre eux.
Finalement,
Inversement: ok.
Finalement,
Soit solution. donc et avec premiers entre eux.
donc .
Sachant , il reste puis .
Inversement: ok.
Finalement,
Soient . Donner une condition nécessaire et suffisante pour que le système
possède un couple solution.
Solution
Si le système possède une solution alors est une condition nécessaire.
Inversement, si alors et donne un couple solution.
Résoudre dans l’équation:
Solution
Soit un couple solution. Posons .
On peut écrire
L’équation devient:
Ainsi est de la forme ou avec .
Inversement, ces couples sont solutions.
Soient et deux entiers naturels avec non nul.
Montrer que, si est le reste de la division euclidienne de par , alors est le reste de la division euclidienne de par .
En déduire
(Suite de Fibonacci)
On considère la suite déterminée par
Vérifier que, pour tout , et sont des entiers premiers entre eux.
Soit . Montrer
Soient et .
Établir
où est le reste de la division euclidienne de par .
Conclure
[<] PGCD et PPCM[>] Nombres premiers
Montrer que pour tout , les entiers , et sont premiers entre eux deux à deux. Que dire des entiers et ?
Montrer que pour tout
Solution
.
donc .
donc
Par produit .
.
donc .
donc .
Par produit .
Soient et deux entiers. Montrer que et sont premiers entre si, et seulement si, et le sont.
Solution
Raisonnons par double implication.
Supposons et premiers entre eux et calculons le pgcd de et . L’entier divise et et donc divise aussi et . On en déduit que vaut : les entiers et sont premiers entre eux.
Supposons et premiers entre eux.
Méthode: On vérifie que est premier avec et avec afin d’affirmer qu’il est alors premier avec .
Introduisons le pgcd de et . L’entier divise et divise aussi car . On en déduit que vaut et donc et sont premiers entre eux. Il en est de même pour et et donc pour et .
Soient .
On suppose . Montrer que .
On revient au cas général. Calculer .
Solution
et .
Ainsi et donc .
Posons . On peut écrire et avec .
Soit .
Montrer que et sont premiers entre eux.
En déduire
Solution
On peut écrire . Par le théorème de Bézout, .
On a
donc
Puisque , on a
or donc
Soient , et trois entiers avec et premiers entre eux.
Montrer .
Que dire de ?
Pour , montrer qu’il existe un couple unique tel que
Calculer .
En déduire que et sont premiers entre eux.
Solution
Unicité: Si et sont solutions alors
donc
Si alors
ce qui est absurde.
On en déduit puis .
Existence: Par la formule du binôme de Newton,
En séparant les termes d’indices pairs de ceux d’indices impairs, on a
avec
On a
Or en reprenant les calculs qui précèdent
donc
La relation qui précède permet d’écrire
On en déduit que et sont premiers entre eux.
Soient et deux entiers relatifs premiers entre eux et un diviseur de .
Montrer
Solution
Unicité: Si est solution alors
Or car et , donc car .
De même, d’où l’unicité.
Existence: Posons et . On a et .
et donc car .
, et donc .
Inversement: Par l’égalité de Bézout on peut écrire et donc car .
On note l’ensemble des diviseurs positifs d’un entier .
Soient deux entiers premiers entre eux. Établir la bijectivité de l’application
Soit . Montrer que les entiers
pour sont deux à deux premiers entre eux.
Solution
Par l’absurde, supposons que et (avec ) ne soient pas premiers entre eux.
Considérons un diviseur premier commun à et . L’entier est diviseur de donc de .
Puisque est premier et diviseur de ou de , il est nécessairement inférieur à et donc assurément diviseur de . Or divise aussi et donc divise .
C’est absurde.
Soient . Pour , on considère l’application
Soient . Calculer .
On suppose que et sont premiers entre eux. Vérifier que l’application est bijective.
Inversement, on suppose l’application bijective, montrer que et sont premiers entre eux.
Solution
Pour tout ,
On a donc .
Supposons et premiers entre eux. Il existe tels que . On vérifie avec
On a donc . On vérifie de même . On en déduit que est bijective (et l’application est sa bijection réciproque).
Supposons l’application bijective. Puisque est élément de , il existe tel que , c’est-à-dire il existe tel que
Par égalité de deux exponentielles imaginaires, il existe tel que
et donc
On en déduit que et sont premiers entre eux.
[<] Nombres premiers entre eux[>] Études arithmétiques
Soit un nombre premier supérieur à .
Montrer que est divisible par .
Soient et la somme de entiers impairs consécutifs. Montrer que n’est pas un nombre premier.
Solution
Notons le premier nombre impair sommé. On a
avec et . Ainsi, est composé.
Montrer que les nombres suivants sont composés:
avec
avec .
Solution
.
Cet entier est composé pour car et .
.
De plus, les équations n’ont pas de solutions car toutes de discriminant négatif. Par conséquent, est composée.
Soient un nombre premier et un entier. Montrer
Soit un naturel non nul. Montrer qu’il existe toujours un nombre premier strictement compris entre et .
Solution
Considérons l’entier . Celui-ci est divisible par un nombre premier inférieur à .
Si ce nombre premier est aussi inférieur à alors il divise (car apparaît comme l’un des facteurs de ce produit) et donc il divise aussi . Ceci est absurde et donc le nombre premier en question est au moins égal à . Finalement, il est strictement compris entre et .
Justifier l’existence de entiers consécutifs sans nombres premiers.
Solution
Considérons les avec . Ce sont entiers consécutifs.
Pour tout , on a donc avec donc .
On suppose que est un entier tel que est premier.
Montrer que est nombre premier.
Solution
Supposons avec . On a alors
On a . On en déduit ou ce qui implique ou .
Ainsi, ne possède que des diviseurs triviaux, il s’agit d’un nombre premier.
Soient et deux nombres entiers supérieurs à . Montrer que, si est un nombre premier, alors et est premier.
Soient des entiers et .
Montrer que si est premier alors est une puissance de 2.
Solution
On peut écrire
On a alors
avec .
On en déduit que , or est supposé premier et donc puis .
Soient et .
On suppose que est un nombre premier. Montrer que est une puissance de 2.
Solution
On peut écrire avec et l’enjeu est d’établir .
Posons et . On a
On peut alors factoriser par et puisque est un nombre premier, on en déduit que ou . Puisque , le cas est à exclure et puisque et , le cas entraîne
Puisque , l’égalité entraîne et finalement est une puissance de 2.
(Morphisme de Frobenius)
Soit un nombre premier.
Pour tout , montrer que le coefficient binomial est un multiple de .
En déduire que pour tous entiers et , .
Soit avec .
On suppose que est premier. Montrer
Inversement, on suppose que est composé. Montrer
Solution
On suppose premier. On sait
donc
ce qui permet d’affirmer que divise l’entier . Or est premier et donc premier avec puisque . Par le théorème de Gauss, on peut alors affirmer que divise .
Supposons maintenant composé. On peut introduire un facteur premier de avec . Nous allons alors montrer que ne divise par ce qui permet de conclure.
Par l’absurde, supposons que soit un entier. On peut écrire
Puisque divise , on peut aussi écrire avec entier et donc
Dans les produits définissant et , on retrouve les mêmes multiples de , à savoir . On peut donc écrire
avec regroupant le produit des multiples de précédents et et non divisibles par .
La relation initiale se simplifie alors pour donner
ce qui entraîne que est divisible par . C’est absurde!
Montrer qu’il existe une infinité de nombres premiers de la forme avec entier.
(Nombres de Fermat)
Pour , on introduit .
On suppose et sont deux entiers naturels distincts. Montrer .
Exploiter cette propriété afin de retrouver le théorème d’Euclide affirmant l’existence d’une infinité de nombres premiers.
[<] Nombres premiers[>] Valuation p-adique
Soient et deux entiers relatifs. Montrer
Soit . Montrer
En déduire que et
Solution
C’est immédiat.
Si alors on peut écrire .
On a alors donc
De plus, et donne .
Par double divisibilité .
ni 2, ni 3 ne sont des carrés d’un entier, donc et .
Soient et deux entiers naturels non nuls premiers entre eux.
Soit un nombre rationnel. On suppose que est entier, montrer que est entier.
Soient et deux entiers non nuls tels que . Montrer qu’il existe tel que et .
On divise un cercle en arcs égaux et l’on joint les points de division de en jusqu’à ce que l’on revienne au point de départ. Quel est le nombre de côtés du polygone construit?
Solution
Le nombre de côté du polygone construit est le plus petit entier tel que .
Posons . On peut écrire et avec .
c’est-à-dire . Ainsi .
On étudie l’équation algébrique
d’inconnue réelle et où les coefficients sont supposés entiers.
Montrer que les solutions de sont des nombres entiers ou des nombres irrationnels.
Solution
Supposons une solution de l’équation avec et premiers entre eux.
En réduisant au même dénominateur, on obtient
Puisque divise , on obtient que divise . Or et sont premiers entre eux donc nécessairement et donc .
Ainsi, les racines rationnelles de sont des nombres entiers et cela répond à la question posée.
Soient et . Déterminer les diviseurs positifs de .
Solution
Soit . Notons la plus grande puissance de telle que .
On peut écrire avec .
Puisque et on a . Or donc, par Gauss: .
Par suite, avec . De plus, donc puis .
Inversement: ok.
Soient et sa décomposition en produit de facteurs premiers.
Quel est le nombre de diviseurs positifs de ?
Solution
Les diviseurs positifs de sont les
avec
Le choix des conduisant à des diviseurs distincts, il y a exactement diviseurs positifs de .
Soit au moins égal à . Montrer que est le produit de ses diviseurs non triviaux11 1 Dans ce sujet, on se limite aux diviseurs positifs. Les diviseurs triviaux de sont et . si, et seulement si, avec nombre premier ou avec et deux nombres premiers distincts.
Soit dont la décomposition primaire est
On note le nombre de diviseurs supérieurs ou égaux à 1 de et la somme de ceux-ci.
Montrer
Solution
Soit diviseur de .
Tout diviseur premier de est aussi diviseur de et c’est donc l’un des .
Par suite, on peut écrire avec .
donc d’où .
Ainsi est de la forme avec pour tout , .
Inversement, de tels nombres sont bien diviseurs de .
Il y a autant de nombres de cette forme distincts que de choix pour les .Pour , il y a choix possibles, au total .
De plus,
Par sommation géométrique
Soit dont la décomposition en facteurs premiers s’écrit
Montrer que la somme des diviseurs positifs de vaut
(Théorème RSA)
Soient et deux nombres premiers distincts, et un entier naturel premier avec le produit .
Justifier qu’il existe un entier tel que .
Montrer que pour tout .
(Triplets pythagoriciens)
On étudie l’équation d’inconnue .
Soit une solution non nulle. Si désigne le pgcd des trois entiers , et , on peut simplifier l’équation par et se ramener à la situation où : nous supposons par la suite être dans ce contexte.
Montrer que , et sont deux à deux premiers entre eux.
Quelles sont les congruences possibles d’un carré modulo ? En déduire que l’une des deux valeurs ou est paire et l’autre impaire.
On suppose que est la valeur paire.
Montrer qu’il existe et entiers tels que et .
Quels sont les triplets solutions de l’équation ?
(Formule d’inversion de Möbius)
Pour , on pose11 1 En particulier, .
Pour , on pose
où la somme porte sur les entiers diviseurs positifs de .
Soient un nombre premier et . Calculer .
Soient et premiers entre eux, vérifier .
En déduire la valeur de pour tout .
On considère une fonction et la fonction définie par
Soit . Vérifier la formule d’inversion
On note le nombre de diviseurs de . Montrer
avec une suite bornée.
(Théorème d’Aubry)
Soient un entier strictement positif et le cercle d’équation .
On suppose que le cercle possède un point à coordonnées rationnelles. On introduit un point à coordonnées entières obtenues par arrondis des coordonnées de . En étudiant, lorsque cela a un sens, l’intersection du cercle avec la droite joignant et , montrer que ce cercle contient un point à coordonnées entières.
[<] Études arithmétiques[>] Petit théorème de Fermat
Soient et un nombre premier. On suppose qu’il existe tel que divise le ppcm de et . Établir que divise ou .
Solution
Notons la valuation -adique :
On sait
Si divise , alors et donc ou . On en déduit que divise ou .
Pour et , on note l’exposant de la plus grande puissance de divisant .
Montrer que .
Plus généralement, calculer . On rappelle que
Solution
car avec produit de nombres impairs.
.
En isolant les multiples de dans le produit décrivant , on obtient
puis
or
avec donne
puis finalement
avec
(Formule de Legendre)
Soient un nombre premier et . Établir
Application : Soient . Montrer
On note l’ensemble des nombres premiers. Pour tout entier , on note l’exposant de dans la décomposition de en facteurs premiers. On note la partie entière de . On note le nombre de nombres premiers au plus égaux à .
Montrer
Montrer que divise .
Montrer que .
Montrer que quand
Solution
Pour suffisamment grand , la somme évoquée existe donc car elle ne comporte qu’un nombre fini de termes non nuls. , parmi les entiers allant de 1 à , il y en a exactement divisibles par , divisibles par , etc…donc
On a
Pour tout ,
or ou 1 donc
De plus, les nombres premiers diviseurs de sont diviseurs d’un entier inférieur à (lemme d’Euclide) et sont donc eux-mêmes inférieur à . Il en découle
car toutes les puissances de nombres premiers intervenant dans la décomposition de divisent .
Notons qu’en fait ce produit désigne
On a
En passant au logarithme:
À l’aide d’une comparaison intégrale on obtient
donc
donc
Par suite,
puis
On en déduit
Ajoutons
par calculs et car et ne différent qu’au plus d’une unité et .
Finalement, une certaine satisfaction.
Soit . Si est l’espression de en base on note
Écrire une fonction calculant et .
Si , vérifier numériquement que .
Prouver que pour tout , .
Calculer en fonction de et .
Soit . Montrer que est une puissance de si, et seulement si, est un entier pair pour tout .
Solution
Tant qu’une puissance de divise , on passe à la puissance suivante:
def v(n): k = 0 p = 1 while n % (2*p) == 0: k = k + 1 p = 2 * p return k
Pour calculer , une solution récursive est possible:
def s(n): if n == 0: return 0 elif n % 2 == 0: return s(n//2) else: return 1 + s((n-1) // 2)
On vérifie qu’aucune valeur n’échoue
for n in range(2, 10**4+1): if v(n) != s(n-1) - s(n) + 1: print(f"Echec pour la valeur {n}")
Posons la valuation de en base . L’écriture en base de se termine par avec un nombre de zéro égal à . L’écriture de commence par les mêmes chiffres mais se termine par . On en déduit .
Pour , donc
Cas: ou . C’est immédiat.
Cas: . Soit . On remarque
Si vaut , son écriture en base de est de la forme avec chiffres . Pour , les chiffres de l’écriture en base de sont les « inverses » des chiffres en base de de puisque . En particulier, . On a donc . Le coefficient binomial est pair.
Si n’est pas une puissance de , on peut écrire avec . Considérons alors . On a et donc . Par conséquent, la valuation en base du coefficient binomial est nulle: c’est entier est impair.
Soit un nombre premier.
Montrer
En déduire que
Solution
On a
donc
Par suite, .
Or est premier et donc puis en vertu du théorème de Gauss.
Par récurrence finie sur
Pour : ok
Supposons la propriété établie au rang
Par la formule du binôme
car pour .
Récurrence établie.
Pour tout , il existe tel que et
Soit un entier. On suppose
Montrer que est un nombre premier
Solution
Pour tout , est premier avec . En effet, un diviseur commun à et est diviseur de et donc de 1.
On en déduit que est premier puisque premier avec chaque naturel strictement inférieur à lui-même.
(Nombres de Carmichael)
Soit un entier supérieur à 2.
On suppose que pour tout facteur premier de , ne divise pas mais divise .
Établir
Solution
Par hypothèse, on peut écrire avec nombres premiers deux à deux distincts.
Soit . Considérons .
Si ne divise pas , le petit théorème de Fermat assure .
Puisque divise , on a encore et donc
Si divise alors divise aussi et donc .
Enfin, chaque divisant et les étant deux à deux premiers entre eux, divise et finalement .
La réciproque de ce résultat est vraie.
Ce résultat montre que le petit théorème de Fermat ne caractérise pas les nombres premiers. Les nombres non premiers satisfaisant le petit théorème de Fermat, sont les nombres de Carmichael. Le plus petit d’entre eux est 561, le suivant 1105.
On désire établir qu’il existe une infinité de nombres premiers de la forme . Pour cela, on raisonne par l’absurde et l’on suppose que ceux-ci sont en nombre fini. On pose le produit de ceux-ci et l’on introduit
On suppose qu’il existe un facteur premier de de la forme . Établir
Conclure en exploitant le petit théorème de Fermat.
Édité le 22-11-2024
Bootstrap 3
-
LaTeXML
-
Powered by MathJax