Logo-de-mathsland.com
Tarask
En Ligne 
Difficile l'arithm√©tique ... 02/07/2011 à 23h31
Soient a,b dans N avec [tex]b\geq a \geq 2[/tex] .
Montrer que si [tex]a^{n}-1[/tex] divise [tex]b^{n}-1[/tex] alors il existe m de N* tel que [tex]b=a^{m}[/tex].

Source : ENS .

P.S: je m'excuse auprès des modérateurs et des admins si j'abuse avec ces oraux.
Code LaTEX 
Espace

evariste

Admin
En Ligne 
Re : Difficile l'arithm√©tique ... 03/07/2011 à 21h31
Bonsoir,

si on prend [tex]a=2[/tex], [tex]b=5[/tex] et [tex]n=2[/tex] on voit que [tex]a^2-1= 3[/tex] divise [tex]b^2-1=24[/tex] sans pour autant que [tex]b[/tex] soir une puissance de [tex]a[/tex]. Est ce qu'il y d'autres condition à l'exercice, genre [tex]n>2[/tex] ?

Sinon les exercices que tu poses sont les bienvenue, ils enrichissent notre site et tout le monde t'en est reconnaissant. Merci.
Code LaTEX 
Espace
Tarask
En Ligne 
Re : Difficile l'arithm√©tique ... 03/07/2011 à 22h13
Bonsoir ,

J'ai pris l'exercice comme il est , je me suis rassuré et je n'ai pas trouvé de détails manquants !
Mais apparemment suite à votre remarque , l'énoncé est , disons , faux . J'essayerai après de travailler avec la condition que vous avez mise , n>2.

Merci .
Espace

evariste

Admin
En Ligne 
Re : Difficile l'arithm√©tique ... 03/07/2011 à 22h55
Rebonsoir,

à vrai dire j'ai essayé de trouver des contre exemples pour trouver les vrais conditions de l'exercice. La condition [tex]n>2[/tex] s'avère en fait insuffisante vu le contre exemple [tex]2^3-1=7 [/tex] divise [tex]9^3-1=728[/tex], On peut penser à imposer [tex]a>2[/tex] mais on a [tex]3^4-1=80[/tex] divise [tex]11^4-1=14640[/tex].

J'ai penser à imposer [tex]a>2[/tex] et [tex]n[/tex] admet au moins un diviseur impaire mais il y a aussi le contre exemple suivant [tex]4^3-1[/tex] divise [tex]22^3-1[/tex]. Voilà, je pense que les conditions de l'exercice ne sont pas si simples.
Amicalement.
Code LaTEX 
Espace
Tarask
En Ligne 
Re : Difficile l'arithm√©tique ... 04/07/2011 à 20h32
Bonsoir M.evariste !
L'énoncé comporte donc des failles (pauvre celui qui l'a eu en oral) , j'essayerai de corriger l'énoncé .
P.S: je crois qu'il faut utiliser la valuation p-adique pour "réparer" l'exercice , je vous tiens au courant si j'arrive à quelque chose .

Merci .
Espace
 jandri
Re : Difficile l'arithm√©tique ... 05/07/2011 à 22h35
Bonsoir,

Le bon énoncé est:

Soient a,b dans N avec [tex]b\geq a \geq 2[/tex] .
Montrer que si pour tout n de N*, [tex] a^{n}-1[/tex] divise [tex] b^{n}-1[/tex] alors il existe m de N* tel que [tex] b=a^{m}[/tex].

Je crois me souvenir que c'est un exercice difficile.
Code LaTEX 
Espace
Tarask
En Ligne 
Re : Difficile l'arithm√©tique ... 05/07/2011 à 22h46
Bonsoir Monsieur Jandri !
Mais Monsieur evariste a bel et bien donné un contre-exemple pour le cas de n=2 ...
Espace

evariste

Admin
En Ligne 
Re : Difficile l'arithm√©tique ... 05/07/2011 à 23h35
Bonsoir,

Ce que Mr Jandri dit est qu'il faut remplacer le fait que la propriété soit vrai pour un [tex]n[/tex] particulier par le fait qu'elle est vrai pour tout [tex]n[/tex].
Code LaTEX 
Espace
Tarask
En Ligne 
Re : Difficile l'arithm√©tique ... 06/07/2011 à 00h16
Bonsoir ,
Je vois , ça veut que s'il existe un certain[tex] n_{0} [/tex]vérifiant la propriété [tex]a^{n_{0}}-1 [/tex]divise [tex]b^{n_{0}}-1[/tex] alors il existera forcément un certain m ....

Je comprends maintenant , l'énoncé de M.jandri est donc tout à fait correct .
Code LaTEX 
Espace

evariste

Admin
En Ligne 
Re : Difficile l'arithm√©tique ... 09/07/2011 à 03h26
Bonsoir,

Voici quelques réflexions sur ce problème. Comme disait Polya : " Si vous ne pouvez pas résoudre un problème, c'est qu'il y a un autre problème plus facile que vous ne pouvez pas résoudre, trouvez le ! "
J'essaye donc d'affaiblir (?) l'énoncé en le ramenant à un énoncé plus simple ( peut être pas !)

D'abord on peut constater que tous les facteurs premiers de l'entier [tex]b[/tex] se trouvent parmi les facteurs de [tex]a[/tex]. En effet si [tex]p[/tex] est un facteur de [tex]b[/tex] qui ne divise pas [tex]a[/tex] alors d'après Fermat [tex]p[/tex] divise [tex]a^{p-1}-1[/tex] qui divise aussi [tex]b^{p-1}-1[/tex] ce qui contredit que [tex]p[/tex] divise [tex]b[/tex].

Je vais supposer un instant qu'on a réussi à montrer la réciproque, càd que les facteurs premiers de [tex]a[/tex] se retrouvent parmi les facteurs premiers de [tex]b[/tex]. Càd acceptons qu'on ait montré que si [tex]a^n-1[/tex] divise [tex]b^n-1[/tex] pour tout [tex]n\geq 1[/tex] alors [tex]a[/tex] et [tex]b[/tex] ont les même facteurs premiers. On va montrer que dans ce cas [tex]b[/tex] est une puissance de [tex]a[/tex]

Il est facile de voir qu'il existe un entier [tex]m[/tex] tel que [tex]b[/tex] divise [tex]a^m[/tex] et donc qu'il existe [tex]b_1[/tex] entier tel que [tex]a^m=bb_1[/tex]. Cependant il serait illusoir d'essayer de montrer que [tex]b_1=1[/tex] car tout [tex]m[/tex] assez grand convient et si [tex]m[/tex] n'est pas la bonne puissance alors certainement [tex]b_1\neq 1[/tex]. Il faut donc imposer une contrainte sur [tex]m[/tex]. Une façon de faire ça est de choisir [tex]m[/tex] de sorte que [tex]b_1[/tex] ne contienne pas un des facteurs premiers de [tex]a[/tex].
On écrit [tex]a=p_1^{\alpha_1}\cdots p_r^{\alpha_r}[/tex] et [tex]b=p_1^{\beta_1}\cdots p_r^{\beta_r}[/tex]. On forme les rapports [tex]\frac{\beta_i}{\alpha_i}[/tex] et on considère [tex]j[/tex] tel que [tex]\frac{\beta_j}{\alpha_j}=\max_i \frac{\beta_i}{\alpha_i}[/tex]. On pose [tex]\frac uv = \frac{\beta_j}{\alpha_j}[/tex]
Alors comme pour tout [tex]i[/tex] on a [tex]u\alpha_i-v\beta_i\geq 0[/tex] alors [tex]b_1=a^ub^{-v}\in \mathbb{N}[/tex] et donc [tex]a^u=b^vb_1[/tex] par ailleurs le facteur [tex]p_j[/tex] ne figure pas dans la decomposition de [tex]b_1[/tex] puisque [tex]\frac uv = \frac{\beta_j}{\alpha_j}[/tex]

On a alors pour tout [tex]n\geq 1[/tex], [tex] b_1^n(b^{nv}-1) =a^{un}-b_1^n=a^{un}-1-(b_1^n-1)[/tex]. Or comme [tex]a^n-1[/tex] divise [tex]a^{nv}-1[/tex] et donc [tex]b^{nv}-1[/tex] et aussi [tex]a^{un}-1 [/tex] alors [tex]a^n-1[/tex] divise [tex]b_1^n-1[/tex] et ceci est vrai pour tout [tex]n[/tex]. Or d'après notre hypothèse [tex]a[/tex] et [tex]b_1[/tex] doivent avoir les mêmes facteurs ce qui contredit le fait que [tex]p_j[/tex] divise [tex]a[/tex] mais ne divise pas [tex]b_1[/tex] à moins que [tex]b_1=1[/tex]

donc [tex]a^u=b^v[/tex]

alors [tex]a^u-1=b^v-1[/tex] divise [tex]b^u-1[/tex] et ceci ne se produit que si [tex]v[/tex] divise [tex]u[/tex] ( excercie, pensez à une division euclidienne de [tex]v[/tex] par [tex]u[/tex] )
donc il existe un entier [tex]m[/tex] tel que [tex]u=mv[/tex] et donc [tex]a^{mv}=b^v[/tex] et donc [tex]a^m=b[/tex]


Pour résumer on aurait résolut l'exercie si on avait montré que l'hypothèse pour tout [tex]n\geq 1[/tex], [tex]a^n-1[/tex] divise [tex]b^n-1[/tex] implique que [tex]a[/tex] et [tex]b[/tex] ont les mêmes facteurs premiers. Et comme on avait montré au début que les facteurs de [tex]b[/tex] sont forcément parmi les facteurs de [tex]a[/tex] ceci revienderait à montrer que les fecteur de [tex]a[/tex] sont parmis les fecteurs de [tex]b[/tex].

Je ne sais pas si cette hypothèse est plus simple ou du même ordre de difficulté que l'exercice originale. Je voulais juste montrer aux élèves une façon de raisonner en mathématique, on essaye de ramener le problème à une forme qu'on espère plus simple. Toute les remarques sont les bienvenues.

Code LaTEX 
Espace
supista
En Ligne 
Re : Difficile l'arithm√©tique ... 14/07/2011 à 19h58
J'ai déjà rencontrer ce problème, c'est un problème posé dans un forum de maths, je vous prie de m'excuser M. l'admin de donner le lien de la solution:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=4556&highlight=masterpiece
Essayer de lire toutes les solution postes posé dans ce lien, c'est très intéressant, à noter que la solution à ce problème ce trouve également dans un livre écris par Titu Andrescu et Harazi que vous pouver trouver dans 4shared.
Pour votre la solution partielle, c'était une idée et une remarque intéressante, mais je pense que cela vous ramène à un problème difficile, mais qu'on peut résoudre par d'autre idées, je vais essayer avec cette piste.
Merci
Espace

evariste

Admin
En Ligne 
Re : Difficile l'arithm√©tique ... 19/07/2011 à 17h30
Salut,

Merci supista pour le lien, les deux premi√®res solutions sont int√©ressantes (pbornsztein et Harazi ). J'ai bien aim√© celle propos√©e par Harazi, j'essayerai de l'exposer ici avec quelques simplifications, en effet dans la finition que propose vess, il ne prend pas en compte que les [tex]\alpha_i[/tex] sont en fait les [tex]r_i[/tex] ce qui simplifie le raisonnement. En revanche je ne suis pas tr√®s √† l'aise avec les autre solutions, par exemple quand vess dit "But as [tex]a[/tex] has order [tex]n[/tex] modulo [tex] p[/tex], [tex]b[/tex] has to be a power of [tex]a[/tex] modulo [tex]p[/tex] (that is, the congruence [tex]b \equiv a^x \pmod{p}[/tex] is solvable)", je ne vois pas d'o√Ļ √ßa sort, j'essaierai de regarder √ßa en d√©tails. En revanche as tu le titre du livre dont tu parles? Encore merci.
Code LaTEX 
Espace
supista
En Ligne 
Re : Difficile l'arithm√©tique ... 21/07/2011 à 17h17
Bonjour,

voilà le lien 4shared pour le livre ( si ça ne marche pas recherche dans google.co.ma du mot "harazi and titu" et tu clic sur le deuxième résultat ):
http://www.4shared.com/document/PxuiuoIF/titu-and-harazi.html

regardes la page 243 ainsi que le chapitre dans lequel se trouve ce problème, c'est très intéressant.
Espace
yasser
En Ligne 
Re : Difficile l'arithm√©tique ... 09/10/2014 à 21h03
bonjour tt le monde

montrer que pour tout n appartient a N*
il existe deux p, q entier naturel unique et non nul tel que n=2 a la puissance p x(2q+1)
montrer que 1+1-2+1-3+++++++++++++1-n est un entier naturel
(1-2 veux dire 1 divisé par 2)
Espace
Cyclotron
En Ligne 
Re : Difficile l'arithm√©tique ... 23/01/2015 à 21h10
BSR au Forum .

C'est un peu Navrant de voir ce Topic de Tarask très Intéressant avec
des Interventions Très Pertinentes
Etre plombé par des Posts , on ne peut plus puérils ....

C'est de cette manière que l' Autre Forum " MathsMaroc Jeunes " a coulé ....

Amicalement . LHASSANE

PS : Mon Bon Souvenir √† Notre Admin evariste et √† Tous les Coll√®gues qui continuent sans rel√Ęche
à Apporter à Ce Forum une forte Plus-Value .....
Espace
Sujet verrouilť par Vous êtes sur l'ancien Forum. Celui-ci est fermé. Cliquer ici pour accéder au nouveau Forum