Savoir & Culture

Salut les clés

Besoin d'aide pour ces quelques questions

1/
soit n ∈ N
calculer pgcd(13,7+13^n)

2/
déterminer les entiers m et n satisfaisant m+n=72 et pgcd(m,n)=9

13 est premiers donc 1 et 13.

1)
T'as essayé de faire la liste des diviseurs des deux nombres ?

2) Naturels, les entiers ?
En tous cas si 9 est leur pgcd, c'est donc qu'il les divise, donc tu peux réécrire la première équation.

Le 24 septembre 2020 à 18:06:01 ChoquantMeme a écrit :
13 est premiers donc 1 et 13.

Du coup tu n'as que deux candidats pour être pgcd. Teste le plus gros, s'il divise tes deux nombres alors c'est le pgcd, sinon c'est l'autre.

Le 24 septembre 2020 à 18:07:38 Jaibuolol a écrit :

Le 24 septembre 2020 à 18:06:01 ChoquantMeme a écrit :
13 est premiers donc 1 et 13.

Du coup tu n'as que deux candidats pour être pgcd. Teste le plus gros, s'il divise tes deux nombres alors c'est le pgcd, sinon c'est l'autre.

Comment je me débrouille avec 7+13^n ?

Tu peux passer par les congruences.
Ou tout simplement factoriser par 13 et regarder ce qu'il se passe.
Ou faire la division euclidienne par 13.

Je vois pas trop comment faire par les congruences

sinon par factorisation

7+13^n = 13 ( 13^(n-1) + 7/13) et après ?

C'est quoi la définition de "X est un multiple de 13" ?

Pour être plus compréhensible :
Si X est multiple de 13, qu'est ce que tu peux écrire ? X = ...

Pour être plus compréhensible :

Si X est multiple de 13, qu'est ce que tu peux écrire ? X = ...

On peut écrire alors X=13k avec k relatif

Voilà, et toi tu viens d'écrire X = 13 * (13^(n-1) +7/13).
Du coup, bah demande toi si c'est de la forme 13k avec k entier relatif

ben non j'ai pas l'impression

tu peux me proposer une correction bien expliquée pour la question 1 stp ?

Pas l'impression ?
Normalement à ce stade tu devrais avoir plus de certitudes que ça
Tu te demandes si 13^(n-1)+7/13 est un nombre entier.
Déjà, "13^(n-1)" est une puissance de 13, donc c'est un entier. (Bon, à part si n=0 ... mais tu peux toujours traiter ce cas ensuite.) Donc tu prends un entier, et tu lui ajoutes 7/13. Bah clairement, le résultat n'est pas entier, t'es d'accord ?

Donc voilà, 13^(n-1)+7/13 n'est pas entier, on en est désormais certains.

T'as donc écrit 13^n + 7 = 13x, avec "x" qui n'est pas entier.
Peut-on avoir 13^n +7 = 13k, avec "k" entier ? Bah dans ce cas on aurait 13x=13k donc x=k, ce qui est absurde (l'un est entier, l'autre non...) Donc non. CQFD, ton nombre n'est pas divisible par 13.

----

Cela dit, la factorisation était la méthode la plus longues parmi celles que je t'ai proposé.
En passant par les congruences c'était immédiat : modulo 13, le "13^n" disparaît et il ne reste que 7, donc directement t'en déduis que ton nombre n'est pas divisible par 13.

(A toi de rédiger tout ça plus formellement / succinctement)

super merci beaucoup pour ton aide je vais étudier tout ça.

pour voir si j'ai fait ça correctement.

on cherche a= pgcd(13,7+13^n)

si n=0, a vaut 1

sinon :

13 est premier donc a est soit 13 soit 1.

on regarde alors si 7+13^n est divisible par 13.

7+13^n divisible par 13 <=> il existe k entier tel que 7+13^n = 13k

<=> il existe k entier tel que k=(13^(n-1)+7/13)

c'est impossible car 13 est entier et 7/13 n'est pas entier donc la somme n'est pas entière

Donc 7+13^n n'est pas divisible par 13.

donc le pgcd vaut 1.

C'est correct ?

d'ailleurs tu peux me montrer comment tu ferais ça avec les congruences et la division euclidienne ?

Ouais c'est bien Tu vas voir que la méthode par congruence est vraiment directe^^

Par congruences :
13^n + 7 = 0^n +7 = 7 (mod 13). Donc 13^n+7 congru à 7 mod 13, et donc 13^n+7 n'est pas divisible par 13.

Par division euclidienne, bah dans le fond c'est exactement pareil que la congruence, en fait je voulais dire que tu pouvais carrément poser la division euclidienne (avec potence etc...)si tu voulais.
Mais du coup bah tu trouves immédiatement que 13^n+7 = 13*13^(n-1)+7, donc le quotient dans la division par 13 c'est 13^(n-1), le reste 7, et donc (puisqu'il y a un reste non nul) ça n'est pas divisible par 13.

Bref, comme tu vois c'est en fait quasi immédiat.

(Evidemment, dans mes deux démos il manque ce que tu as écrit au début de la tienne, comme quoi les deux seuls candidats à tester sont 1 et 13)

ok et pour le 2 je fais comment ?

je commence comme ça :

on travaille sur N.

pgcd(m,n)=9

donc il existe k dans N tq m+n = 9k

et après je bloque un peu