Salut,

Je n'ai ni le sujet ni l'énoncé en ma possession et ils ne sont pas non plus sur l'île...

je suppose que est une suite numérique. Quelle est son expression ?

Bonjour si d=pgcd(n,p) et d1=pgcd(un,up). d divise n et p donc ud divise un et up donc ud divise d1. Donc d1=a(ud) avec a entier. d1 divise un et up donc a(ud) divise un et up d'ou ad divise n et p.On en deduit ad divise le pgcd de n et p cad d. Donc a=1 par suite d1=ud.

Salut,

admettons que np; alors n=qp+r (où q et r sont des entiers naturels) avec 0r<p. On a alors Un=Upq+Ur où 0Ur<Up. En déroulant l'algorithme d'Euclide, on obtient PGCD(Un;Up)=PGCD(Up;Ur)=...=Ur_n (où r_n est le dernier reste non nul, donc le PGCD de n et de p) d'où PGCD(Un;Up)=U.PGCD(n;p). ^^ cqfd

J'aimerais bien voir (si ça n'est pa la même) ta démonstration...

Au fait, la question de cinnamon me fait douter : U est bien un entier naturel non nul, et pas une suite...

Peut-être que je suis passée totalement à côté, mais si U est un entier, pourqoui avoir mis n et p en indice et pas sur la même ligne ?

Bonsoir,

D'abord je voudrais remercier tous ceux qui ont répondu. En réalité, j'ai posé la question pour un de mes collègues qui enseigne en TS. Comme je ne savais pas répondre sur le champ, je lui ai proposé de poster sa question sur le forum de l'Île.

Il ne connaissait pas votre site et j'ai donc posté cet après midi la question pour lui et je lui ai en même temps montré l'intérêt qu'on pouvait avoir, pour nous mêmes et surtout pour nos élèves, à utiliser toutes les compétences qui existent ici.

Il doit normalement s'inscrire lui-même et repréciser sa question. Celle-ci n'a semble-t-il pas été comprise. U désigne bien une suite comme le suggère cinnamon... et la réponse proposée par Cauchy ne correspond pas à la question.

Bonsoir patrice

Ce résultat me rappelle des souvenirs : s'agit-il de la suite de Fibonacci ?

Kaiser

Non, a priori, l'exercice n'a rien à voir avec la suite de Fibonacci, mais je ne l'ai peut être pas bien lu.

Voici, pour ceux que ça intéresse, un lien vers l'énoncé de l'exercice (c'est un fichier pdf) :

J'avais pas tilté qu'il s'agissait de suites

un comble pour Cauchy

Re bonsoir

Est-ce que la démonstration compliquée en question utilisait l'algorithme d'Euclide ?

Kaiser

Bonjour

Je n'ai pas trouvé de démonstration "immédiate" (utilisant le résultat de la question précédente par exemple). C'est un exercice connu (on le trouve dans plusieurs livres de Terminale, dans un cas plus général, mais toujours avec des questions préalables gudant la recherche...)

A démontrer : pgcd (2ⁿ-1,2^p-1)=2^d-1, avec d = pgcd (n,p).


Une démarche possible (inspirée d'un exo Nathan déclic 1998):

Soit D = pgcd (2ⁿ-1,2^p-1)

- Tout d'abord d|n donc 2^d-1|2ⁿ-1,
en effet : n=dm, donc

de même 2^d-1|2^p-1

et par conséquent

- D'autre part, d'après Bezout, il existe k et k' tels que kn-k'p=d

On a

donc

or donc

et comme 2ⁿ-1|2^kn-1 et 2^p-1|2^k'p-1, alors D|2^kn-1 et D|2^k'p-1

donc

d'où la conclusion.

Une autre démarche (inspirée d'un livre d'exercices du début des annes 70) :

En supposant n supérieur à p

on commence par montrer que le reste de la division euclidienne de aⁿ-1 par a^p-1 est a^r-1, où r est le reste de la division euclidienne de n par p.


n=pq+r avec 0 r < p



donc , ce qui montre (puisque 0rnn-1 par a^p-1 est a^r-1.

Ensuite il ne reste qu'à appliquer l'algorithme d'Euclide, et on obtient :

pdcd(aⁿ-1,a^p-1) = pdcd(a^p-1,a^r-1)=.....=a^d-1.


- sauf erreur et aux fautes de frappe près (un peu fastidieux à écrire....)

Mais bon, tout ceci n'est pas "immédiat", j'en ai parlé avec quelques amis et je reste convaincu que quelque chose a dû nous échapper...

Si quelqu'un trouve quelque chose de plus simple et dans l'esprit de l'exercice....

Bonjour à tous ...

Je n'ai pas le corrigé de l'exercice mais j'ai une solution qui utilise les questions précédentes ...

Soit n et p deux entiers naturels non nuls

En appliquant l'algorithme d'Euclide aux entiers n et p, on construit une suite de restes (r(m)) définit par :
r(0)=n;r(1)=p et pour tout entiers naturels m :
r(m+2) = q(m+1)r(m+1) - r(m)  avec 0<= r(m+2) <= r(m+1)

Le pgcd de n  et p étant le dernier reste non nul que l'on note r(k) (r(k+1)=0)

Montrons que pour tout m : pgcd(U(r(m)),U(r(m+1)))= pgcd(U(r(m+1)),U(r(m+2)))

pgcd(U(r(m)),U(r(m+1)))= pgcd(U(r(m)-q(m+1)r(m+1)),Ur(m+1)) (d'apres la question precedente)
pgcd(U(r(m)),U(r(m+1)))= pgcd(U(r(m+2)),U(r(m+1)))


Par une récurence immédiate sur m on obtient :
pgcd(U(n),U(p))= pgcd(U(r(0)),U(r(1)))= pgcd(U(r(1)),U(r(2)))= ... =pgcd(U(r(k)),U(r(k+1)))= pgcd(U(r(k)),U(0))= pgcd(U(r(k)),0) = U(r(k))= U(pgcd(n,p))

Voila ...

D'accord et merci Matouille2b (et bonjour)

En fait je cherche un argument (s'il existe) permettant d'écrire quasi-directement à partir de la question précédente :

pgcd(U_n,U_p) = pgcd(U_p,U_r), et alors de "dérouler" Euclide pour arriver au résultat.

Ce que tu as fait finalement, mais je cherche encore plus expéditif (est-ce possible ?....)



PS : au fait dans mon post précédent les 2 sont devenus des a, (mais comme ça mrche pour a 2, pas trop de bobo )