Nombres parfaits

Fin de partie · February 2020

Nahar:

Pourquoi faire simple quand on peut faire compliqué? C'est le sens de ta question? B-)

Moi-même je me suis pris les pieds dans le tapis, bon courage pour terminer.

PS:
Je me suis trompé de fil:

L'égalité $\boxed{\displaystyle (n!+1)\times (1-(n+1)(n-1)!)+((n+1)!+1)\times (n-1)!=1}$ permet de conclure et donne une manière directe de montrer ce qu'on veut.
Mais il faut reconnaître que j'ai eu un peu de mal à l'établir. :-D

nahar · February 2020

Fin de partie
Désolé je n'avais pas lu ton égalité; la mienne n'était pas fausse.tu peux le vérifier.

Fin de partie · February 2020

Nahar:

Je ne dis pas qu'elle est fausse mais je ne sais pas ce que tu veux en faire.

L'égalité que j'ai présentée plus haut est de la forme $a((n+1)!+1)+b(n!+1)=1$ , les $a,b$ sont déterminés.
Si elle est vraie, et elle l'est, cela permet de dire immédiatement, grâce au sens évident du théorème de Bézout, que les nombres $(n+1)!+1$ , $n!+1$ sont premier entre eux.

nahar · February 2020

Je voulais juste dire à Oshine qu'il avait commencé une bonne méthode se basant seulement sur la divisibilité.
Il lui manquait juste cette remarque ou toute égalité semblable pour aboutir.

OShine · February 2020

Toute égalité semblable ?

Je trouve que $d$ divise $n n!$ donc $d$ divise $n$ ou $d$ divise un élément de $[|1,n|]$.

nahar · February 2020

Toute égalité semblable= $\boxed{\displaystyle (n!+1)\times (1-(n+1)(n-1)!)+((n+1)!+1)\times (n-1)!=1}$, par exemple
S'il change un peu, il trouve $d$ divise $n$ et non pas $nn!$.
C'est une méthode qu'il a du voir en classe.
Je veux juste l'encourager dans cette voie.
Etant prof moi-même, au lycée certes, je conseille à mes élèves de bien maitriser le cours et toutes les techniques
avant de s'attaquer aux exercices dits de perfectionnement.
En mpsi c'est bien de cela qu'il s'agit.

Fin de partie · February 2020

OShine: $n^2$ divise $n.n!$. Est-ce que $n^2$ divise $n$ ou un élément parmi : $1,2,...,n$?

Nahar:
http://www.les-mathematiques.net/phorum/read.php?5,1939110,1940350#msg-1940350

PS:
OShine: Je ne sais plus qui, pardon, plus haut a suggéré de ne considérer que les nombres premiers qui divisent $n.n!$.
Si tu veux continuer sur cette lancée, il va probablement falloir prendre en compte cette recommandation.

OShine · February 2020

@Fin de partie
Non.

J'avoue que cet exercice m'a embrouillé je préfère laisser de côté.

lourrran · February 2020

Sage décision.

A mon avis, un exercice qui s'étend sur plus de 15 messages, faut oublier... et éventuellement repartir à 0 quelques jours plus tard.
Un exercice qui s'étend sur plus d'une journée, idem.

Par contre, en mode 'individuel' (sans forum), cogiter sur un exercice pendant 1 ou 2 jours, alors là, oui, c'est utile.

OShine · February 2020

@Lourran

Oui j'ai passé trop de temps dessus mais je note sur mon cahier les points d'incompréhension j'y reviendrai quand j'aurais le temps.

Je ne peux pas laisser tomber des choses que je ne comprends pas dans mon livre, sinon ça me donne envie d'abandonner les maths, je suis comme ça.
Ça devient une obsession quand je ne comprends pas une chose je reste bloqué dessus.

Par contre les autres exercices si j'y arrive pas je zappe.

Mes les exercices de mon livre je veux tous les comprendre.

Fin de partie · February 2020

OShine:

Si on reprend l'égalité que tu as trouvé:

$(n+1)!+1 -(n!+1) = (n+1) n!+1 -n!-1= n n!$

Propriété:
Si aucun nombre premier ne divise simultanément deux entiers $a$ et $b$ alors $a$ et $b$ sont premiers entre eux.

Supposons qu'il existe un nombre premier $p$ qui divise $n!+1$ et $(n+1)!+1$.
D'après l'égalité ci-dessus $p$ divise aussi $n.n!$.

Les facteurs premiers de $n.n!$ sont ceux de $n!$.

En effet, si $p$ premier divise $n!$ il est clair qu'il divise $n.n!$.
Si un nombre premier $p$ divise $n.n!$ il divise $n$ ou il divise $n!$ (il peut diviser les deux) mais puisque $n$ divise $n!$ il divise donc $n!$.

Mais $n!$ et $n!+1$ sont premiers entre eux (ce sont deux entiers consécutifs, cela te rappelle quelque chose?)
ce nombre premier $p$ ne peut pas diviser $n!+1$ ce qui est contradictoire. Pour lever la contradiction, il faut que ce $p$ n'existe pas. Donc il n'existe aucun nombre premier qui divise simultanément $n!+1$ et $(n+1)!+1$, ces deux nombres sont premiers entre eux.

noix de totos · February 2020

Un exercice sous forme de boutade (O Shine, tu ne vas pas aimer...) : soit $n$ un entier parfait. Montrer que
$$\sum_{d \mid n} \frac{1}{d} = 2.$$

nahar · February 2020

Bonsoir,
Alors, je procède ainsi:
Soit $d$ un diviseur de $(n+1)!+1$ et $n!+1$ (ou tout simplement $d=((n+1)!+1)\wedge(n!+1)$.
On a: $(n+1)!+1+n=(n+1)(n!+1)$.
$d$ divise $n!+1$ donc $d$ divise $(n+1)(n!+1)$(Si $a/b$ alors $a/(bc)$ pour tout $c$).
D'où $d$ divise $(n+1)!+1+n$.
Or $d$ divise $(n+1)!+1$ donc $d$ divise $(n+1)!+1+n-((n+1)!+1)$.(Si $a/b$ et $a/c$ alors $a/(b-c)$.)
Ainsi $d$ divise $n$.
Par conséquent $d$ divise $n!$.(propriété du produit ci-dessus)
Or $d$ divise $n!+1$ donc $d$ divise $n!+1-n!$.
Ainsi $d$ divise $1$.
Et enfin $d=1$

OShine · February 2020

@Noix de toto

Un exercice de niveau ENS non ? Je préfère ne pas m'y frotter ::o

@Nahar
Bien joué.

@Fin de partie
Ok merci.

noix de totos · February 2020

Non, non, la réponse tient en à peine une ligne...à condition de bien manipuler ces sommes portant sur des diviseurs, qui ne sont pas plus compliquées, au fond, que les sommes "traditionnelles".

noobey · February 2020

Non non l'exo est très simple mais intéressant de voir si tu y arrives!

OShine · February 2020

Ok merci je vais chercher.

lourrran · February 2020

Intéressant. L'astuce ne vient pas tout de suite, mais quand on a trouvé l'astuce, la démo tient en effet en 1 ligne.

Fin de partie · February 2020

Il est vraiment l'heure de me coucher.
Dans l'exo proposé par Noix de totos je n'avais pas vu que $n$ n'était pas quelconque mais parfait :-D Je commençais à me poser des questions. Noix de totos aime beaucoup la fonction sigma. Une solution tient en effet en une seule ligne si on se rappelle la définition d'un nombre parfait et si on connait le changement de variable standard dans ce type de sommes.

Autrement, on essaie sur un exemple. $6$ est un nombre parfait.

$1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$

Si on réduit le plus simplement au même dénominateur que va-t-on obtenir en dénominateur et que va-t-on obtenir en numérateur?

PS:
En fait, il vaut mieux trouver la formule générale pour tout $n$ entier non nul pour le nombre $\displaystyle \sum_{d| n} \frac{1}{d}$, cela ne coûte pas plus cher, ensuite, l'appliquer au cas où $n$ est un entier parfait.

noix de totos · February 2020

Bon. Fin de Partie a révélé l'astuce, qui d'ailleurs n'en est pas une.

Fin de Partie a écrit:

\sum_{d \mid n} f(d)
il vaut mieux trouver la formule générale pour tout $n$ entier non nul pour le nombre $\displaystyle \sum_{d \mid n} \frac{1}{d}$

Il faut surtout retenir le point essentiel suivant : l'application $d \mapsto d^{\, \prime}$ à qui tout diviseur $d$ de $n$ associe le diviseur $d^{\, \prime}$ de $n$ tel que $dd^{\, \prime} = n$ est une bijection.

Cela permet le changement de variable $d \to n/d$ dans toute somme portant sur les diviseurs de $n$ et en particulier
$$\sum_{d \mid n} f(d) = \sum_{d \mid n} f(n/d).$$
Ce principe, appliqué par exemple à la fonction $f = \textrm{id}^{-1}$ (ou $f = \textrm{id}$, ça revient au même) fournit immédiatement
$$\sum_{d \mid n} \frac{1}{d} = \frac{\sigma(n)}{n}.$$
D'où la réponse à la petite question que j'ai posé hier. Soit dit en passant, pour ceux qui veulent obtenir une estimation non triviale de l'ordre moyen de $\sigma$, il vaut mieux effectuer ce changement de variable, comme je l'avais montré le mois précédent dans une discussion avec Al-Kashi, je crois.

Question subsidiaire. Quelle égalité simple obtient-on en appliquant ce principe à la fonction $f = \textrm{id}^{-k}$, où $k \in \mathbb{Z}_{\geqslant 1}$ est fixé ?

OShine · February 2020

Je ne vois pas en quoi l'exercice est simple je ne comprends pas un mot de la correction. C'est du chinois pour moi.

Poirot · February 2020

Tu ne vois pas plus loin que les formules du cours alors.

noix de totos · February 2020

Mince...Moi qui pensais aider ! Tant pis.

À toutes fins utiles, voilà la la correction : soit $n \geqslant 2$ entier parfait, de sorte que $\sigma(n) = 2n$. Ainsi
$$\sum_{d \mid n} \frac{1}{d} = \frac{\sigma(n)}{n} = 2.$$
Pour ceux qui s'en sentent le courage, voici une extension : Montrer que, pour tout $n \geqslant 3$ entier quelconque
$$\sum_{d \mid n} \frac{1}{d} \leqslant \log \sqrt n + 3.$$
Si on la mène bien, la démonstration fait...deux lignes.

OShine · February 2020

@Poirot

Si. Mais je n'ai pas le niveau pour ces exercices. Je l'avais prédis.
Les formules du cours de MPSI sont déjà assez compliquées comme ça et pas facile à digérer.
Je n'ai pas compris l'histoire de la bijection et l'histoire de $id$. Quel rapport avec sigma ?
Bref ce genre d'exercice je peux peut être le comprendre mais avec une correction très détaillée. Faut savoir être modeste dans la vie.

@Noix de Totos
Des exercices qui ne sont pas de mon niveau ne vont pas m'aider mais m'enfoncer et me décourager.

C'est pas un exercice qui tombera a CCP par exemple. Et mon niveau actuel est plutôt les exercices de CCP.

Ce sont des exercices de niveau Mines X ENS qui sont largement hors de ma protée.

noix de totos · February 2020

L'arithmétique "élémentaire" est une branche de la théorie des nombres dans laquelle on étudie l'arithmétique avec des outils non perfectionnés : pgcd, ppcm, congruences, petit théorème de Fermat, théorème chinois, résidus quadratiques, fractions continuées, fractions de Farey, équations diophantiennes simples, et certains cours ajoutent une introduction aux nombres $p$-adiques.

Les branches plus avancées de la théorie des nombres (théorie analytique, théorie algébrique, théorie transcendantale, théorie probabiliste, etc) utilisent des outils puissants provenant de l'analyse, de l'algèbre, de la théorie ergodique, des probabilités, etc.

Dans ce fil où tu poses des questions, je n'ai jamais évoqué ces branches difficiles de la théorie des nombres, qui demandent au mieux une spécialisation, voire une professionnalisation.

Après, dire que tel ou tel exercice que j'ai mis ici est du ressort des "mines/ponts/centrales" ou pas est absolument impossible à dire, car il n'y a pas de telles classifications en arithmétique, cette dernière étant une branche des maths plutôt enseignée "en marge" dans l'enseignement supérieur en France.

OShine · February 2020

J'ai lu des milliers d'exercices des concours. Je connais le niveau de chaque concours et le type d'exercice qui y tombe à l'oral comme à l'écrit.

Cet exercice en CCP c'est impossible. Il est beaucoup trop difficile.

Pas besoin d'être dans une branche perfectionnée pour faire des exercices difficiles. Je ne parle pas du niveau MASTER maths (je n'ai pas fait de maths après ma prépa MP) mais du niveau BAC+2 et des concours de prépa scientifiques.
Le niveau peut être très élevé mais uniquement avec des outils au programme de MPSI-PCSI-PC-MP-PSI.

J'ai lu certains rapports où les rapports du Jury disent : "question extrêmement difficile" plusieurs fois dans des rapports de sujet Centrale.

Mais vous parlez de choses difficiles dans vos interventions et vous dites que c'est élémentaire. Ça ne l'est pas pour tout le monde. Je ne comprends pas grand chose à ce que vous dites.

Dans mon bouquin qui est de niveau MPSI, il y a des exercices extrêmement difficiles. Vous allez me dire si je n'arrive pas à les faire que c'est pourtant que des notions élémentaires ?

Poirot · February 2020

Oui, les notions que ces exercices font manipuler sont élémentaires. Ça ne les empêche pas d'être des exercices difficiles, mais il n'y a pas d'outils sophistiqués.

lourrran · February 2020

Un nombre parfait, c'est quoi, c'est un nombre $n$ tel que la somme de ses diviseurs donne $2n$.

C'est la seule information qui caractérise un nombre parfait. C'est notre seule bouée. On va forcément devoir utiliser cette information pour faire cette démonstration.

Et bonne nouvelle, cette propriété ressemble pas mal à ce qu'on nous demande de démontrer :
- dans les 2 cas (la définition d'un nombre parfait, et l'égalité à démontrer) , on a une somme.
- le nombre de termes est le même , c'est le nombre de diviseurs de $n$
- on retrouve le facteur 2 : on a une somme qui vaut 2n, et on nous demande de montrer qu'une autre somme vaut 2.

On veut montrer qu'une certaine somme donne 2. Multiplions par n des 2 côtés, ça revient à montrer que la somme des $\frac{n}{d}$ donne $2n$

Maintenant, je vais affirmer une chose , tu pourras dire que c'est le théorème de Lourrran si tu veux : $d$ est un diviseur de $n$ si et seulement si $\frac{n}{d}$ est un diviseur de $n$
Je ne le démontre pas, ça ne ma paraît pas utile. Mais c'est le point essentiel, tu dois en être convaincu.
Ce résultat là, c'est ce que Noix de Totos énonçait en parlant d'une bijection entre l'ensemble des diviseurs de n et ce même ensemble

Je redis encore la même chose, mais sur un exemple, avec n=6 : les diviseurs de 6 sont 1,2,3,6, et si on regarde l'autre série de nombres : 6/1, 6/2, 6/3, 6/6, on retombe sur la série des diviseurs, mais en ordre décroissant
Idem avec un nombre non parfait , n=10 ; les diviseurs de 10 sont 1,2,5,10, les n/d sont 10/1, 10/2, 10/5 et 10/10 : on retombe sur les 4 mêmes nombres, mais dans l'autre ordre.

La somme des $\frac{n}{d}$, c'est donc tout simplement la somme des diviseurs de $n$.

Donc pour n'importe quel nombre $n$, si on s'intéresse à la somme des nombres $n/d$ avec $d$ diviseur de $n$, c'est la même chose que la somme des diviseurs de $n$ .
Et dans le cas d'un nombre parfait, ça donne $2n$ CQFD.

OShine · February 2020

Merci j'ai démontré le théorème de Lourran en 2 lignes.

$\displaystyle\sum_{d \mid n} \dfrac{n}{d} = \displaystyle\sum_{(n/d) \mid n} \dfrac{n}{d} $

Ah peut être j'ai compris si je pose $D=n/d$

J'obtiens $S=\displaystyle\sum_{D \mid n} D = 2n$ car $n$ a $2n$ diviseurs c'est tout ?

Poirot · February 2020

$n$ n'a pas $2n$ diviseurs.

OShine · February 2020

Oui pardon $n$ est parfait la somme de ses diviseurs vaut $2n$.

noix de totos · February 2020

Je reprécise mon propos : le mot "élémentaire" ne signifie pas "simple" dans la caractérisation des différentes branches de la théorie des nombres, il veut dire ce que j'ai dit plus haut : on n'utilise pas d'outils perfectionnés, dont j'ai mentionné quelques exemples plus haut.

L'exercice $n \ \textrm{parfait} \Longrightarrow \displaystyle \sum_{d \mid n} \frac{1}{d} = 2$ est, au premier abord, plutôt difficile, j'en conviens.

Mais lorsque l'on a une "indication" du genre "il se fait en une ligne", ça sous-entend :

(i) ou bien il n'est pas si difficile que ça ;

(ii) ou bien il y a une astuce, pas nécessairement simple à trouver, pour le résoudre.

Dans les deux cas, on cherche par réflexe l'aide d'un outil non perfectionné (ceux que j'ai cité plus haut), et on n'a pas besoin de disposer de connaissances particulières pour le résoudre.

Si tu regardes bien les annales, il y a des exos CCP qui sont exactement dans ce moule-là.

Ici, ce type d'exo peut permettre à un prof / jury qui le pose de vérifier si le candidat possède les points très simples concernant les diviseurs d'un entier. Ici, il s'agit de la correspondance entre diviseurs que j'ai évoqué ci-dessus. Si on a du mal à voir ça, alors on teste avec un exemple simple.

Exemple. Prenons $n=24$. Les diviseurs sont $\{1,2,3,4,6,8,12,24\}$. L'idée est de noter que, puisque chacun de ces diviseurs est associé de façon unique à un autre dont le produit des deux fait $24$, en mettant $\frac{1}{24}$ en facteur dans la somme, on retrouve au numérateur la somme de tous les diviseurs de $24$ :
$$\sum_{d \mid 24} \frac{1}{d} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{12} + \frac{1}{24} = \frac{1}{24} \left( 24 + 12 + 8 + 6 + 4 + 3 + 2 + 1 \right) = \frac{\sigma(24)}{24} = \frac{5}{2}.$$
Prenons maintenant un nombre parfait, par exemple $n=6$ (c'est d'ailleurs pour ça qu'on les nomme "parfait" : Dieu a fait le monde en $6$ jours). La somme des inverses des diviseurs de $6$ peut être effectuée comme suit
$$\sum_{d \mid 6} \frac{1}{d} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = \frac{1}{6} \left( 6 + 3 + 2 + 1 \right) = \frac{\sigma(6)}{6} = \frac{2 \times 6}{6} = 2$$

OShine · February 2020

D'accord merci, en effet sur un exemple concret c'est beaucoup plus clair !

lourrran · February 2020

Un peu sur le même thème .. un peu, voici une énigme qui m'a beaucoup plu :

On a une rangée avec 100 ampoules, numérotées de 1 à 100.

Au début de l'expérience, toutes les ampoules sont allumées.
Je vais prendre tous les nombres entre 1 et 100.
Quand je prend le nombre $i$, j'actionne l'interrupteur de toutes les ampoules dont le numéro est un multiple de i ;

Doncc à la première étape, j'éteins toutes les ampoules, puisque tous les numéros sont des multiples de 1.
A l'étape 2, j'allume les ampoules de n° pair
A l'étape 3, j'actionne les ampoules dont le n° est multiple de 3... c'est à dire que j'allume un certain nombre d'ampoules, et j'en éteins un certain nombre.
etc jusqu'à l'étape 100.
A la fin, quelles ampoules sont allumées ?

Rescassol · February 2020

Bonjour,

C'est rigolo, seules les ampoules d'indice carré sont éteintes.

N=100
Tab=[True]*(N+1)
for n in range(1,N+1):
    for k in range(n,N+1):
        if not k % n:
            Tab[k] = not Tab[k]
    
print(Tab[1:])
for n in range(N+1):
    if not Tab[n]:
        print(n)

Cordialement,

Rescassol

LOU16 · February 2020

Bonsoir,

Oui, c'est normal, car seuls les carrés d'entiers possèdent un nombre impair de diviseurs positifs.

lourrran · February 2020

Rescassol a écrit:

C'est rigolo, seules les ampoules d'indice carré sont éteintes.

C'est exactement la réflexion que je me suis faite dans les mêmes circonstances.

Dans une classe de lycée, quand on commence la programmation, ça peut être un petit TP très sympa, pour réconcilier les élèves avec l'arithmétique.

Fin de partie · February 2020

Noix de Toto a écrit:

Il faut surtout retenir le point essentiel suivant : l'application d->d? à qui tout diviseur d de n associe le diviseur d? de n tel que dd?=n est une bijection.

En effet,

FDP a écrit:

Une solution tient en effet en une seule ligne si on se rappelle la définition d'un nombre parfait et si on connait le changement de variable standard dans ce type de sommes.

http://www.les-mathematiques.net/phorum/read.php?5,1939110,1940868#msg-1940868

Le changement de variable auquel je pensais: $d\rightarrow n/d$

OShine · February 2020

Comment on montre que l'application :

$\mathcal D(n) \longrightarrow \N \\ d \mapsto d \times d=n$ est une bijection ?

Poirot · February 2020

C'est absolument n'importe quoi.

OShine · February 2020

En effet, je n'ai pas compris cette histoire de bijection.

Chat-maths · February 2020

Cette histoire de la bijection, c'est de dire que $\mathcal{D}(n) \to \mathcal{D}(n)$, $d \mapsto \frac{n}{d}$ est une bijection (attention aux ensembles de départ et d'arrivée!). Et donc, comme toute bijection, elle peut être utilisée pour procéder à un changement d'indice.

OShine · February 2020

Je vais essayer de rectifier.

$u : \mathcal D(n) \longrightarrow \mathcal D(n) \\ d \mapsto d' \ \text{tel que} \ d \times d'=n$ est une bijection.

Il faut montrer que pour tout $d' \in \mathcal D(n)$ il existe un unique $d \in \mathcal D(n)$ tel que $u(d)=d'$?

OShine · February 2020

Quel est le rapport entre la bijection et le changement d'indice ?

Chat-maths · February 2020

Pour tout ensemble fini $A$, $B$, $f: A \to B$ une bijection, $u : A \to \mathbb{C}$ une application (encore une fois, je mets $\mathbb{C}$, mais n'importe quel groupe abélien fait l'affaire), alors $\sum\limits_{x \in A}u(x) = \sum\limits_{y \in B}u(f^{-1}(y))$. Ce qu'on appelle un "changement d'indice", c'est en fait ça.

En d'autre termes, une bijection, c'est jamais rien qu'une manière de "changer les étiquettes" sur les objets, ou encore, de "parcourir" différement la somme (parcourir a plus de sens si $A = B$). Par exemple le truc de la somme "parcourue à l'envers", c'était ça avec $A = B = \{0,\cdots,r\}$ et $f: j \mapsto r - j$.

Fin de partie · February 2020

OShine: Dans le produit $d.d'=n$ où $n$ non nul est fixé si tu fixes $d$ aussi, tu as une seule valeur pour $d'$.
C'est ce que veut dire cette histoire de bijection.
Les diviseurs d'un nombre sont en tandem. Les nombres $1$ et $n$ sont en tandem par exemple car $n\times 1=n$ B-)-

Le truc auquel il faut faire attention parfois est que le "tandem" peut être composé du même nombre.
Exemple si on prend $n=4, 2\times 2=4$

Dit autrement, la bijection dont il est question plus haut ne fixe aucun diviseur d'un entier $n$ non nul si $n$ n'est pas un carré parfait.

OShine · February 2020

D'accord merci.

Je fixe $d' \in \mathcal D(n)$. Je dois résoudre $dd'=n$ ce qui donne $d=\dfrac{n}{d'}$
Je trouve bien un unique $d$.

On a donc $d=u^{-1} (d')$

Et donc $u^{-1} (d) = \dfrac{n}{d}$

Si on en revient à la somme $\displaystyle\sum_{d \in \mathcal D(n)} \dfrac{1}{d} = \cdots $

Mais là je n'ai pas trop compris comment appliquer la, bijection à cette somme.