soustraire la moitié ....pour avoir a la fin 1

[midorima]

Bonjour j'ai ici un exercice qu'on m'a donné que je trouve difficile
Le voilà :
On choisit un nombre N>=2 puis on lui fait différentes opérations :
On lui soustrait son plus grand diviseur different de lui
et la, on a un nouveau nombre N1
Ensuite on prend N1 et en lui soustrait a son tour son plus grand diviseur
Different de lui et la on a un nouveau nombre N2
On refait la même opération jusqu'à ce qu'il reste 1
Par exemple si N=30 on soustrait de lui 15
Es alors on a N1=15 ensuitre on soustrait de lui 5 et donc on a 10
Ensuite on soustrait 5 pour avoir 5 ensuite on soustrait 1 pour avoir 4
Ensuite on soustrait 2 pour avoir 2 ensuite on soustrait 1 pour a la fin avoir 1
On a donc refait l'opération 6 fois
Maintenant si N=2016 combien de fois doit on refaire l'opération pour avoir 1

Je pense qu'une fois le travail commencé ça devient comme un jeu
Mais je bloque tout au début
Comment trouver le plus grand diviseur de 2016 alors la comment trouver N1
Alors je voudrais des conseil pour débuter l'exercice
Merci
-----

[gg0]

Pour un nombre pair, quel est le plus grand diviseur ?
Pour un impair multiple de 3 ?
...

Cordialement.

[phys4]

Bonjour,
Vous pouvez facilement encadrer le nombre d'opérations :
- si le nombre est une puissance de 2, vous aurez un nombre d'opérations égal à son exposant.
- dans le pire des cas, vous avez une division par 2 une fois sur 2, car un plus petit facteur premier impair donnera un résultat pair. Cela vous permet de calculer un nombre max d'opérations.

Au revoir et bon amusement.

[midorima]

Pour un nombre pair je pense que le plus grand diviseur est sa moitié
Pour un impair multiple de 3 je pense que c'est le résultat de sa division par 3 non?

[A voir en vidéo sur Futura]

[midorima]

Phys4
2016 n'est pas une puissance de 2
Et donc ça fait partie de l'autre cas
Et je n'ai pas très bien compris ton explication pour le 2eme cas

[gg0]

Midorima,

va jusqu'au bout de ce qui se passe pour un nombre pair. Et pense, pour un nombre impair, par quoi on multiplie le plus grand diviseur.

NB : Faire ce genre d'exercice demande d'avoir un minimum d'imagination et de regarder ce qui se passe. D'ailleurs, avec 2016, c'est vite trouvé !!!

[midorima]

Eeuuuh
Je suis franchement désolé
N n'est pas egale a 2016
Mais N=2016 ^155
Sinon 2016 je l'aurai fais tout seul
Il y aurais un moyen de modifier le premier message

[gg0]

Si n est un nombre pair, on reste avec sa moitié et on peut recommencer jusqu'à avoir un impair
Si n est un impair multiple de 3, on enlève son tiers, puis, comme on a un pair, on divise le reste par 2, on a obtenu le tiers.

Donc déjà, avec ces méthodes tu vas tomber sur un nombre nettement plus petit. lequel ?

J'insiste, je ne vois pas pourquoi tu fais ce genre d'exercice de type olympiades si tu ne cherches pas toi-même ce qui se passe. Tu ne vas pas retenir par cœur des milliers d'exercices très particuliers. C'est à toi de chercher, sinon ça ne te sert à rien !!

[midorima]

Je fais les olympiades parce que avec les exercices de ce types requierent du raisonnement et de la logique et on a pas besoin de faire des cours pour cela (enfin dans la plus part du temps) avec les olympiades on peut vraiment faire appel a l'intelligence, n'est tu pas d'accord avec moi ?
Contrairement au exercices de cours qui sont de simples applications
Je sais très bien que je ne vais pas tout retenir
Et ce n'est pas tout les exercice que je trouve que je poste ici
A chaque exercice je m'y met a 100% coir a 120%
Mais c'est comme je ne suis pas un génie
Les exercices que je n'ai vraiment pas su faire je demande des conseil
Pour que je puisses les faire
J'ai vraiment essayé de le faire mais je bloque au début voilà pourquoi je n'aarive pas a décoller ce n'est pas que je ne cherche pas mais je ne trouve pas

[midorima]

Et puis j'ai je le sais pour les nombres pairs et impairs
Mais comment trouvais la moitié de 2016^155

[phys4]

Tout nombre se décompose en une multiplication de nombres premiers.
Si ce nombre a un exposant N, sa décomposition en facteur premier est la multiplication dans laquelle le nombre de chaque facteur est multipliée par l'exposant.

Lorsque l'on effectue la soustraction du plus grand multiple, cela revient à trouver le plus petit facteur premier puis à le remplacer dans la multiplication par ce facteur moins un.
Vous pouvez faire l’exercice avec 2016, dont la décomposition est très simple.
Il est donc facile de prévoir le nombre total d'opérations pour 2016 puissance 155

Bonne suite.

[gg0]

Midorima,

ces exercices demandent, contrairement à ce que tu dis, d'excellentes connaissances de cours, par exemple ici sur la divisibilité. Et en plus la volonté de trouver seul (même quand on a lu 300 corrigés de ces exercices, on ne sait pas faire le 301-ième si on n'a pas essayé de résoudre seul.
Je t'ai donné de grosses indications, pour l'instant tu attends encore qu'on fasse le travail à ta place ... Je t'en donne deux encore, mais j'ai presque tout dit :
* décomposition en facteurs premiers
* combien d'étapes pour N=2⁵x3² ? (bien entendu sans calculer N)

Cordialement.

[midorima]

Gg0
Je n'attend pas qu'on me fasse l'exercice
J'ai juste eu des problème de connexion
Je n'ai donc pu ni me connecter ni voir les messages
Maintenant je vais faire avec ce que vous avez postez

[midorima]

Re bonjour

Phys4
1008(2) -1008=1008(2-1)
Bon bref j'ai compris
En faisant l'exercice avec le nombre 2016 j'ai trouvé que l'opération se repetait 13 fois
Tu dis qu'il est très facile de trouver pour 2016^155
Ce ne serait pas 13*155=2015
Puisque pour un facteur c'est 13 alors pour 155 c'edt 2015
Je te donne raison Gg0 cela nécessite des cours de divisibilité

Gg0
En decomposant 2016= 2^5 *3² *7
Je n'ai compris ce que tu veux dire "combien d'etapes pour N"
Tu veux dire combien de fois refaire l'opération ?
En 9 étapes pour 3²*2^5
Mais ce n'est pas N je pense que tu as du oublier 7
Sinon ce serait 13 fois
Mais pourquoi veux tu le décomposer
Dans l'énoncé il y a bien l'exemple avec 30 et il n y a eu aucune décomposition

Tu

[gg0]

Je n'avais pas oublié 7, je voulais voir si tu réfléchissais vraiment à ce qui se passe en prenant simplement 3²*2^5 :
En 5 étapes on arrive à 3², en deux étapes de plus, à 3, puis en deux étapes encore à 1. Donc il faut 9 étapes.

Pour 2016 = 3²*2^5, dans ce nombre d'étapes on arrive à 7, puis on passe à 6, à 3 et en deux étapes à 1, ce qui donne effectivement 13 étapes.

Reste à justifier pourquoi pour 2016^155 il faut exactement 155 fois plus d'étapes.

Cordialement.

[midorima]

2016^155=(2^5*3²*7)^155
Donc = 2^(5*155) * 3^(2*155) * 7^155
Est ce que le nombre d'etapes est 2015 ?

[phys4]

La réponse est facile à trouver donc, mais comme dit gg0 il faut le justifier
je crois que les olympiades dépendent aussi de la qualité de la démonstration.

Il faudrait montrer que le nombre d'étapes et la somme des étapes pour chaque nombre premier composant l'entier initial. Je pense que tous les éléments sont réunis pour faire cela très proprement.

A plus.

[midorima]

Je pense que c'est évident
Le nombre d'étape pour un facteur est x
Comme c'est le même facteur qui se répète 155 fois
Donc 155x
Je ne voie comment justifier autrement
Mais c'est vrai que les justifications et les démonstrations n'ont jamais étaient mon fort

[gg0]

Il se trouve que ce raisonnement n'est pas parfait, parce qu'on ne traite les facteurs indépendamment. En pratique, on commence obligatoirement par le facteur 2 (nombres pairs), puis on traite les facteurs 3 (nombre impair multiple de 3), puis il reste la puissance de 7.
Donc une bonne explication est un peu plus longue, d'autant qu'il faut justifier pourquoi on fait ainsi.
En particulier, saurais-tu justifier, pour un nombre quelconque, quel est son plus grand diviseur ? disons pour un nombre uniquement divisible par 11, 13 et 23 ? par exemple 470327, quel est son plus grand diviseur (sachant qu'il est un produit de facteurs premiers 11, 13 et 23) ?

Cordialement.

[midorima]

Pour savoir quel est son plus grand diviseur
Je le divise par son plus petit facteur avec 1 comme exposant
470237=11²*13²*23
470327÷11=42757
Je pense que c'est son plus grand diviseur
Il faut commencer par divisé sur son plus petit facteur pour trouver le plusgrand diviseur, non ?

[gg0]

C'est cela, peux-tu le prouver ?

Attention, c'est le plus petit facteur premier sauf dans un cas.

[midorima]

gg0
Je m'excuse pour mon incompréhension
Mais tu veux que je prouve quoi exactement
Et le seul cas ou ce n'est pas le plus petit facteur premier, c'est lequel ?

[midorima]

Si c'est pour 470327 bein
C'est très logique et évident
Y a t il une démonstration autre que ce que j'ai deja fait ?

[gg0]

"C'est très logique et évident" n'est pas une démonstration, seulement une affirmation que tu y crois.
"Y a t il une démonstration autre que ce que j'ai déjà fait ? " ben .. comme tu n'as pas démontré, oui, il y a une démonstration. J'en ai même deux en tête. Et tu n'as même pas remarqué que dans le cas général, le plus petit diviseur est 1 et que ce n'est pas celui-ci qui sert pour 470327; alors que c'est celui qui sert dans certains cas !
Donc non seulement tu n'as rien prouvé, mais tu n'as même pas vraiment compris ce que tu faisais !!
Quel est le plus grand diviseur de 781 ? De 787 ?

Cordialement.

[midorima]

Re bonjour
Alors
781 = 11 ÷71
71 ne peut pas se factoriser parce qu'il est premier
71>11
Donc le plus grand diviseur de 781 est 71

787 est premier
Il ne peut pas se factoriser
787 ÷ 29=27,13...
29>27,13...
Donc 787 est premier
Donc son plus grand diviseur est lui même ( je ne suis pas sur si c'est lr nombre lui même ou le 1)

Et pour la démonstration, est elle algébrique ou c'est de l'ecrit ?

[gg0]

Il faut que tu sois cohérente. Si le plus grand diviseur de 787 est lui-même, alors le plus grand diviseur de 781 est lui-même, pas 71.
Donc parlons de diviseurs stricts :
Quel est le plus grand diviseur strict de 787 ? Justifie-le.
Quel est le plus grand diviseur strict de 781 ? Justifie-le.

Maintenant, prenons le cas de 21 : Quel est son plus grand diviseur strict ? Que se passe-t-il quand on le soustrait ? Pourquoi obtient-on finalement 3 ? Que fait-on pour 3 ?

"Et pour la démonstration, est elle algébrique ou c'est de l'ecrit ? " A priori, l'un ou l'autre ou un mélange des deux. Ce qui compte c'est que soient seulement appliquées des règles de maths (c'est ça qui caractérise une démonstration). Par exemple ta phrase "Donc le plus grand diviseur de 781 est 71" n'est pas l'application d'une règle de maths, seulement de ta propre conviction. Même si auparavant tu utiles des règles de maths.

[midorima]

Le plus grand diviseur strict de 787 est 1
La justification : en divisant 787 sur des nombres premiers a un moment le quotient est plus
Petit que le diviseur
Donc 787 est un nombre premier

Le plus grand diviseur strict de 781 est 71
Justification : en divisant 781 sur des nombres premiers on trouve qu'il est divisible par 2
Facteur seulement 71 et 11
Comme 71>11
Donc 71 est le plus grand diviseur strict de 781

21= 7*3
Je n'ai pas bien compris
Que se passe t il quand on le soustrait , pourquoi obient on finalement 3, que fait on pour 3

Pour le soustraire
21-7=14
14-7=7
7-1=6
6-3=3
3-1=2
2-1=1

Sinon je n'ai pas compris le reste

[gg0]

Bon,

je vais détailler les idées qui permettent de traiter correctement le cas de 2016^155 :
1 * Si un nombre est premier, son plus grand diviseur strict est 1, puisque ses seuls diviseurs sont 1 et lui-même.
2 * Si un nombre n est composé (pas premier), soit p son plus grand diviseur strict et q=n/p. comme p<n, on a q>1. pour tout nombre r compris entre 1 et q (1<r<q), n/r n'est pas un entier (donc pas un diviseur de n) car n/q=p<n/r<n/1=n et il n'y a pas de diviseur de n entre p et n. Il n'y a donc pas de diviseur entre 1 et q, donc q est le plus petit diviseur de n différent de 1; q est aussi premier car s'il avait un diviseur strict autre que 1, ce serait un diviseur de n. Donc trouver le plus grand diviseur struict de n se fait en cherchant son plus petit facteur premier q et en prenant p=n/q.
3 * Si un nombre composé est pair, son plus grand diviseur strict est donc sa moitié, et quand on l'a soustrait, il reste sa moitié. l'opération peut continuer tant que le reste est pair (a un diviseur premier 2); cas particulier : si on tombe sur le reste 2 (pas composé), en enlevant son plus grand diviseur 1, on obtient 1. Il y a une étape à chaque fois.
4 * Si un nombre composé impair n est un multiple de 3, son plus grand diviseur strict est donc son tiers, quand on soustrait on trouve un nombre pair qui est 2n/2, qui donne par le règle 3 l'impair n/3. On peut recommencer tant qu'il y a des facteurs 3, avec 2 étapes à chaque fois; cas particulier : si on tombe sur le reste 3 (pas composé), en enlevant son plus grand diviseur 1, on obtient 2 qui en une étape donne 1. il y a deux étapes à chaque fois
5 * Si un nombre composé non divisible par 2, 3 et 5, n, est un multiple de 7, son plus grand diviseur strict est donc ....

(Je te laisse rédiger le cas 5).
En appliquant la règle 3 jusqu'au bout, puis la règle 4 jusqu'au bout puis la règle 5, on voit que le nombre d'étapes est 5*155+2*2*155+4*155=2015.

Les preuves qui sont dans les différents cas sont des mélanges de calculs et de raisonnements en français.

Cordialement.

[midorima]

Pour le cas 5
Si un nombre composé non divisible par 2, 3 et 5, n, est un multiple de 7, son plus grand diviseur strict est donc p=n÷7
Parce que comme tu l'as dit dans le cas 1 :
''Donc trouver le plus grand diviseur struict de n se fait en cherchant son plus petit facteur premier q et en prenant''
Hors le puisque c'est un multiple de 7 , c'est donc son plus petit facteur
Vu qu'il n'est divisible ni par 2 ni par 3 ( donc pas aussi par 6) ni par 5
Donc pour trouvé p son plus grand diviseur ,on divise n le nombre sur 7
p=n/7
Je pense que c'est ça

Enfin
Merci pour ta patience
Mais j'ai une dernière question
Pour démontrer quel est le plus grand diviseur, la justification est elle la règle ?
Et quel était le reel but de me faire revoir le plus grand diviseur dans cet exercice ?