Inscription / Connexion Nouveau Sujet
3 questions d un exercice d arithmétique que je ne comprend pas
Bonjour,
Serait -il possible d'avoir de l'aide pour les 3 questions de cet exercice d'arithmétique auxquelles je ne trouve pas la réponse svp ?
merci !
1)Montrer que pr tt entier naturel non nul k et pr tt entier naturel x :
(x-1)(1+x+x^2+....+x^(k-1))=(x^k) -1
-> j'ai réussi
2) a/soit n un entier naturel non nul et d un diviseur positif de n : n=dk
montrer que a^d -1 est un diviseur de a^n -1
-> j'ai réussi
b/ Déduire de la question précédente que 2^2004 - 1 est divisible par 7, par 63 et par 9.
-> pour 7 et 63 j'ai dit que 2004=668*3 donc k=668 et d=3, on obtient 2^3 - 1=7
cependant je n'arrive pas à repondre pour 9
3)Soit m et n deux entiers naturels non nuls et d leur pgcd
a/ on definit m' et n' par m=m'd et n=n'd
en appliquant le theoreme de Bezout à m' et n', montrons qu'il existe des entiers relatifs u et v tels que mu-nv=d
-> je ne comprend pas
b/ on suppose u et v strictement positifs
montrer que :
(a^(mu)-1) - (a^(nv)-1)a^d = a^d -1
-> c'est bon
montrer ensuite que: PGCD (a^(mu) -1 , a^(nv)-1)= a^d -1
-> je n'y arrive pas
c/Calculer, en utilisant le résultat précédent, le PGCD de 2^63 - 1 et de 2^60 - 1.
-> j'ai réussi
Merci beaucoup
Bonjour 9*7=63 donc s'il est divisible par 63 il est divisible par 9.
Pour la 3) tu remarques que m' et n' sont premiers entre eux donc il existe u et v (Bezout) tels que m'u+n'v=1 .En multipliant par d on obtient le resultat recherche.
J'ai une question pour la 3) :
J'ai suivi la méthode que Cauchy m'a indiquée mais je trouve mu + nv = d et non pas mu - nv = d, est-ce normal ?
Enfin serait-il possible d'avoir une indication pour la question 3-b/ :
montrer ensuite que: PGCD (a^(mu) -1 , a^(nv)-1)= a^d -1 ?
Merci beaucoup !
Pellote tu peux tres bien choisir u et w tels que m'u-n'w=1 en fait il suffit de prendre w=-v. Sinon pour ta question c'est a^(d-1) ou a^(d)-1.
D'accord, je n'étais pas sure.
sinon pour la question c'est a^(d) -1 est le PGCD de a^(mu)-1 et de a^(nv)-1
Pour ta question utilises l'expression que tu as obtenu avant en faisant l'algorithme d'euclide.(division de a^(mu)-1 par a^(nv)-1).
Ensuite il te faut utiliser le fait que d divise n pour pouvoir utiliser le 2)a).
Si tu vois pas je detaillerais.
j'ai essayé de faire le calcul a^(mu)-1 par a^(nv)-1 mais je tourne en rond et je retombe sur le calcul du départ... enfin j'arrive à cela : a^(d +nv)-1 / a^(nv)-1 ce qui n'avance pas les choses ... :s
En fait comme (a^(mu)-1) - (a^(nv)-1)a^d = a^(d) -1
alors a^(mu)-1=(a^(nv)-1)a^d+a^(d) -1
donc le reste de la division euclidienne de a^(mu)-1 par a^(nv)-1 est bien
a^(d) -1 car il est strictement inferieur à a^(nv)-1 car d<nv donc
pgcd(a^(mu)-1,a^(nv)-1)=pgcd(a^(nv)-1,a^(d)-1) or d'apres 2a) comme d divise nv on a a^(d)-1 qui divise a^(nv)-1 donc
pgcd(a^(nv)-1,a^(d)-1)=a^d-1 d'ou le resultat.Voila 
oui, je n'avais pas fais attention au schéma de la division euclédienne... merci beaucoup pour ces réponses précises et rapides !!
Annuler
connectez vous