Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

PGCD et div euclidienne

Posté par
dede83magic
31-01-19 à 17:27

Bonjour j'ai dû mal à résoudre un exercice d'arithmétique :

On suppose que a et n sont des entiers, tels que a3 et n2.
1) Déterminer le quotient qnet le reste rn dans la division eucliedienne de an par (a-1).
2) En déduire que qn(a-1) = n(a-1)       (= pgcd)

j'ai réussi la question 1) mais la 2 je ne trouve pas..

3) On suppose que x, p, q sont des entiers naturels non nuls, avec x2. On note d=pq.
a) Montrer que (xd-1) | (xp-1)(xq-1).
b) montrer que pour tout k, (xkp-1)(xd-1) = (xkq-1)(xd-1) = (xd-1).
c) en utilisant un couple de Bézout pour la relation d=pq, en déduire que (x[/sup]-1) = (x[sup]p-1)(xq-1)

A part la question 1 ne n'ai pas trouvé...

Posté par
gerreba
re : PGCD et div euclidienne 31-01-19 à 17:30

Bonsoir,
a^n -1 =(a-1)(.....?.....)

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 17:37

an-1 = (a-1) * ak*1n-1-k

Posté par
gerreba
re : PGCD et div euclidienne 31-01-19 à 17:49

D'où a^n=...

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 17:51

C'est pour la question 1? Parce que j'ai trouvé Rn = 1 et Qn = (a-1) * ak*1n-1-k

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 18:26

salut

q_n n'est pas ce que tu dis ...

a^n - 1 = (a - 1)q_n  avec q_n = ...

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 18:29

je comprend pas.. on a an-1 = an-1n = (a-1)(ak1n-1-k)

donc an = (a-1)(ak1n-1-k) +1
et on a la div euclidienne de an par a-1 non?

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 18:37

certes ... et qui qui est ton quotient ?

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 18:38

et franchement les puissances de 1 ...

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 18:40

du coup qn= ak

Posté par
etniopal
re : PGCD et div euclidienne 31-01-19 à 18:44

pourquoi trainer des 1k ?

r(n) = 1 et q(n) = 1 + a + a² +....+ an-1  (somme de n termes .

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 18:49

aucune idée

je comprend pas comment à partir de ça on peut en déduire que les 2 pgcd sont égaux : on doit utliser la propriété qui dit si d=ab alors a' b' entiers tels que a=da' et b=db' avec a'b'=1 ?

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 18:58

q = 1 + a + a^2 + ... + a^{n- 1} = 1 - 1 + a - 1 + a^2 - 1 + ... + a^{n - 1} - 1 + n => q = (a - 1)p + n

si d divise a - 1 et q alors il divise n
si d divise a - 1 et n alors il divise q

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 19:07

ah!! j'avais pas pensé à simplifier comme vous l'avez fait..
Merci!

Pour les dernières questions mis à part des exemples qui me permettent de comprendre la questioon je n'arrive pas à démontrer les égalités..

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 19:43

p=dm et q = dn avec (m, n) = 1

x^p - 1 = (x^d)^m = 1 = ... (voir 1/ ...

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 19:43

carpediem @ 31-01-2019 à 19:43

p=dm et q = dn avec (m, n) = 1

x^p - 1 = (x^d)^m - 1 = ... (voir 1/ ...

Posté par
dede83magic
re : PGCD et div euclidienne 31-01-19 à 20:58

merci bien, j'ai fini la question 3a et 3c il me reste plus que la 3b

si qqn pourrait m'aider, merci

Posté par
carpediem
re : PGCD et div euclidienne 31-01-19 à 22:17

b/ se déduit de a/ ...



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1768 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !