3 petits exos d'arithmétique (mpsi)

[Anonyme]

Bonjour,

j'aurais besoin d'un peu d'aide concernant ces trois exercices.

.. Soient a, m, n, trois entiers. On pose D = pgcd(a^m-1,a^n-1) et d =
pgcd(m,n), et je dois montrer que D = a^d-1 J'arrive à montrer que a^d-1
divise D en factorisant a^m-1 et a^n-1 par a^d-1, mais je n'arrive pas à
montrer que c'est le plus grand diviseur commun. Je ne sais pas si c'est
une bonne idée de vouloir montrer que 1+a^m'+...+a^(d*(m'-1)) et
1+a^n'+...+a^(d*(n'-1)) sont premiers entre eux (avec m=dm' et n=dn').

.. m est un entier impair et n un entier quelconque. Je dois montrer que
2^n+1 est premiers avec 2^m-1. Je dois avouer que je n'ai pas beaucoup
d'idée..

.. a et b sont premiers entre eux. Trouver le pgcd d de a^3-b^3 et (a-b)^3.
Je ne connais pas le résultat. J'arrive juste à montrer que a-b divise d
et que d divise (a-b)^2. Peut-être que dans un premier temps le simple
résultat suffirait à m'aider.


Merci d'avance pour votre aide

--
albert

[Anonyme]

On Thu, 10 Mar 2005 11:23:47 +0100, albert junior
wrote:


>. m est un entier impair et n un entier quelconque. Je dois montrer que
>2^n+1 est premiers avec 2^m-1. Je dois avouer que je n'ai pas beaucoup
>d'idée..
>
>. a et b sont premiers entre eux. Trouver le pgcd d de a^3-b^3 et (a-b)^3.
>Je ne connais pas le résultat. J'arrive juste à montrer que a-b divise d
>et que d divise (a-b)^2. Peut-être que dans un premier temps le simple
>résultat suffirait à m'aider.
a-b divisant les deux nombres le pgcd cherché est a-b fois le pgcd des
quotients
et par des différences ce pgcd des quotients doit faire 1

[Anonyme]

Alain Pichereau a écrit:
[color=green]
>>. a et b sont premiers entre eux. Trouver le pgcd d de a^3-b^3 et (a-b)^3.
>>Je ne connais pas le résultat. J'arrive juste à montrer que a-b divise d
>>et que d divise (a-b)^2. Peut-être que dans un premier temps le simple
>>résultat suffirait à m'aider.
>
> a-b divisant les deux nombres le pgcd cherché est a-b fois le pgcd des
> quotients
> et par des différences ce pgcd des quotients doit faire 1[/color]

justement ca me semble faux.
Exemple : pour a = 8, b = 5, 8^3-5^3 = 387, (8-5)^3 = 27, le pgcd de ces
deux nombres est 9 et non pas 3.

--
albert

[Anonyme]

albert junior a écrit :
> Bonjour,
>
> j'aurais besoin d'un peu d'aide concernant ces trois exercices.
>
> . Soient a, m, n, trois entiers. On pose D = pgcd(a^m-1,a^n-1) et d =
> pgcd(m,n), et je dois montrer que D = a^d-1

Suppose par exemple m>n et écrit m=q*n+r (division euclidienne)
Ensuite, écrit "développe" a^m-1 pour faire apparaitre a^n-1 et a^r-1
Il faut enfin conclure en utilisant un pseudo algorithme d'Euclide

[Anonyme]

albert junior a écrit :
> Bonjour,
>
> j'aurais besoin d'un peu d'aide concernant ces trois exercices.
>
> . Soient a, m, n, trois entiers. On pose D = pgcd(a^m-1,a^n-1) et d =
> pgcd(m,n), et je dois montrer que D = a^d-1

Suppose par exemple m>n et écrit m=q*n+r (division euclidienne)
Ensuite, "développe" a^m-1 pour faire apparaitre a^n-1 et a^r-1
Il faut enfin conclure en utilisant un pseudo algorithme d'Euclide

[Anonyme]

Nougy a écrit:
[color=green]
>> . Soient a, m, n, trois entiers. On pose D = pgcd(a^m-1,a^n-1) et d =
>> pgcd(m,n), et je dois montrer que D = a^d-1
>
>
> Suppose par exemple m>n et écrit m=q*n+r (division euclidienne)
> Ensuite, "développe" a^m-1 pour faire apparaitre a^n-1 et a^r-1
> Il faut enfin conclure en utilisant un pseudo algorithme d'Euclide[/color]

Merci beaucoup, ca marche très bien.
sympa comme solution

--
albert

[Anonyme]

albert junior a écrit :

> . a et b sont premiers entre eux. Trouver le pgcd d de a^3-b^3 et (a-b)^3.
> Je ne connais pas le résultat.


Le résultat dépend du fait que a-b est divisible par 3 ou pas...

[Anonyme]

On Thu, 10 Mar 2005 18:21:51 +0100, albert junior
wrote:

>Nougy a écrit:
>[color=green][color=darkred]
>>> . Soient a, m, n, trois entiers. On pose D = pgcd(a^m-1,a^n-1) et d =
>>> pgcd(m,n), et je dois montrer que D = a^d-1
>>
>>
>> Suppose par exemple m>n et écrit m=q*n+r (division euclidienne)
>> Ensuite, "développe" a^m-1 pour faire apparaitre a^n-1 et a^r-1
>> Il faut enfin conclure en utilisant un pseudo algorithme d'Euclide[/color]
>
>Merci beaucoup, ca marche très bien.
>sympa comme solution
>
>--
>albert
>[/color]
je ne vois pas de différence avec la méthode que j'ai donnée ce matin

[Anonyme]

On Thu, 10 Mar 2005 17:36:08 +0100, albert junior
wrote:

>Alain Pichereau a écrit:
>[color=green][color=darkred]
>>>. a et b sont premiers entre eux. Trouver le pgcd d de a^3-b^3 et (a-b)^3.
>>>Je ne connais pas le résultat. J'arrive juste à montrer que a-b divise d
>>>et que d divise (a-b)^2. Peut-être que dans un premier temps le simple
>>>résultat suffirait à m'aider.
>>
>> a-b divisant les deux nombres le pgcd cherché est a-b fois le pgcd des
>> quotients
>> et par des différences ce pgcd des quotients doit faire 1[/color]
>
>justement ca me semble faux.
>Exemple : pour a = 8, b = 5, 8^3-5^3 = 387, (8-5)^3 = 27, le pgcd de ces
>deux nombres est 9 et non pas 3.[/color]
effectivement mais la méthode que j'ai proposée marche sans pb
car ca revient à chercher le pgcd
de (a-b)^2 et de a^2+ab+b^2
et la différence est 3ab et non ab
(erreur de calcul)
d'où l'histoire effectivement du 3 de Nougy
>

[Anonyme]

Alain Pichereau a écrit :
[color=green]
>>
>
> je ne vois pas de différence avec la méthode que j'ai donnée ce matin[/color]

Désolé s'il y a eu doublon mais je ne vois pas votre message de ce matin
concernant cet exercice...

[Anonyme]

Nougy a écrit:
> Alain Pichereau a écrit :
>[color=green][color=darkred]
>>>
>>
>> je ne vois pas de différence avec la méthode que j'ai donnée ce matin[/color]
>
>
> Désolé s'il y a eu doublon mais je ne vois pas votre message de ce matin
> concernant cet exercice...[/color]

Moi non plus. Peut-être qu'il va arriver plus tard, ou alors vous avez
oublié de le poster. Pas grave en tout cas et merci à vous deux.

--
albert

[Anonyme]

[énoncé]

m=nq+r (division euclid)
a^m-1=(a^n-1+1)^q*a^r-1
et on développe la parenthése selon le binôme
alors D=pgcd(a^n-1,a^r-1)
et on continue : c'est l'"histoire" du dernier reste non nul



Concernant l'exercice 2 :

> . m est un entier impair et n un entier quelconque. Je dois montrer
> que 2^n+1 est premiers avec 2^m-1. Je dois avouer que je n'ai pas
> beaucoup d'idée..

Je n'ai réuissi qu'à me ramener au cas m>n (m = n est facile):

Si m c | 2^m (2^(n-m) + 1)

Puisque les deux nombres sont impairs, c ne peut pas être pair.
Donc c | 2^(n-m) + 1, et on se ramène au même problème avec n remplacé
par n-m. Reste à répéter ça jusqu'à ce que n<m.

Dans le cas restant, je n'ai pas d'idées...

[Anonyme]

Hibernatus a écrit:

(merci pour le repost)

[color=green]
> > . m est un entier impair et n un entier quelconque. Je dois montrer
> > que 2^n+1 est premiers avec 2^m-1. Je dois avouer que je n'ai pas
> > beaucoup d'idée..
>
> Je n'ai réuissi qu'à me ramener au cas m>n (m = n est facile):
>
> Si m
> c | 2^m + 2^n => c | 2^m (2^(n-m) + 1)
>
> Puisque les deux nombres sont impairs, c ne peut pas être pair.
> Donc c | 2^(n-m) + 1, et on se ramène au même problème avec n remplacé
> par n-m. Reste à répéter ça jusqu'à ce que n
> Dans le cas restant, je n'ai pas d'idées...[/color]

J'avais fait la même chose, mais je n'arrive pas non plus à aller plus
loin dès que n<m. Merci.

--
albert

[Anonyme]

On Thu, 10 Mar 2005 19:47:04 +0100, Nougy wrote:

>Alain Pichereau a écrit :
>[color=green][color=darkred]
>>>
>>
>> je ne vois pas de différence avec la méthode que j'ai donnée ce matin[/color]
>
>Désolé s'il y a eu doublon mais je ne vois pas votre message de ce matin
>concernant cet exercice...[/color]
pas grave du tout
en fait l'expli est probablement que mon message est daté du 1er mars
2005 à 10h55 et peut être que certains logiciels de news classent par
date?
(j'ai récupéré le mien dans la file à 10h56 ; Hibernatus l'a aussi
récupéré, cf il le cite dans son message)

expli de ce 1er mars : ma pile (celle sur la carte mère) est tombée en
rade hier soir je suis allé en chercher une autre
mais pour la remise à jour de date-heure
j'ai tout remis à jour sauf ......le jour
toujours aussi fûté...AP

[Anonyme]

Hibernatus a écrit:
[color=green]
> > . m est un entier impair et n un entier quelconque. Je dois montrer
> > que 2^n+1 est premiers avec 2^m-1. Je dois avouer que je n'ai pas
> > beaucoup d'idée..
>
> Je n'ai réuissi qu'à me ramener au cas m>n (m = n est facile):
>
> Si m
> c | 2^m + 2^n => c | 2^m (2^(n-m) + 1)
>
> Puisque les deux nombres sont impairs, c ne peut pas être pair.
> Donc c | 2^(n-m) + 1, et on se ramène au même problème avec n remplacé
> par n-m. Reste à répéter ça jusqu'à ce que n
> Dans le cas restant, je n'ai pas d'idées...[/color]


Un ami vient de me donner une solution.

Soit p un diviseur premier commun à 2^n+1 et 2^m-1
2^m = 1 [p]
2^(2n) = 1 [p]

Soit k l'ordre de 2 modulo p.
k divise m impair donc est impair. Donc k divise n.
Mais alors 2^n = 1 [p] et comme on avait 2^n = -1 [p] p = 2 ce qui est
impossible.

--
albert

[Anonyme]

albert junior wrote:

> Soit p un diviseur premier commun à 2^n+1 et 2^m-1
> 2^m = 1 [p]
> 2^(2n) = 1 [p]

Ah oui, passage au carré, je n'y ai pas pensé.

> Soit k l'ordre de 2 modulo p.
> k divise m impair donc est impair. Donc k divise n.
> Mais alors 2^n = 1 [p] et comme on avait 2^n = -1 [p] p = 2 ce qui est
> impossible.

C'est rapide, en fin de compte

[Anonyme]

Hibernatus a écrit:

>
> C'est rapide, en fin de compte


C'est ca qui est bien avec l'arithmétique