Faut utiliser le fait que PGCD( a ; b ) = PGCD( b ; r ) où r est le reste dans la division euclidienne de a par b.
Tu poses ta division de 2^35-1 par 2^21-1, et tu choisis un quotient de sorte à faire disparaître le 2^35.
De fil en aiguille, tu finiras par tomber sur le PGCD (dernier reste non nul via l'algorithme d'Euclide).

comme ceci par exemple ?

http://sketchtoy.com/69350453

Oui mais attention, soustraire -2^14 revient à ajouter 2^14.
Donc il reste -1 + 2^14 et non -1 - 2^14.

yes petite erreur de signe désolé

donc on a
http://sketchtoy.com/69351786

ben du coup je fais les divisions euclidiennes successives

sachant que pgcd(a,b) = pgcd(b,r)

du coup la valeur des nombres diminue

ouais bon c'est plié en fait

faut juste connaître l'astuce

donc j'ai trouvé que le pgcd vaut 2^7 - 1

vous pouvez confirmer ?

https://www.wolframalpha.com/input/?i=gcd%282%5E21-1+%3B+2%5E35-1%29
Correct.

tabu olol ?

question supplémentaire :

si on a

a=b[c]

alors

pgcd(a,c)=pgcd(b,c) ?

comment le démontrer ?

Faut prouver que chaque pgcd divise l'autre. Ainsi, ils seront nécessairement égaux.
Pour ça, reviens à la définition : que signifie a=b[c] ?

il existe k relatif tq a-b = kc

ie c divise a-b

Du coup pgcd(a,c) divise quoi ?

a-b ?

oui mais t'as mieux que ça
pour montrer que pgcd(a,c) divise pgcd(b,c) il suffit de montrer qu'il divise b (et c mais ça tu l'as déjà)

tu peux me formaliser ça stp ? j'ai du mal à saisir

on part de a=b[c]

donc on a

a-b = kc

on a aussi

b-a=-kc

et ensuite ?

Tu sais que pgcd(a,c) divise a et c par définition, et tu as a-b=kc... qu'est-ce que tu peux faire avec cette égalité pour obtenir que pgcd(a,c) divise b ? Je peux pas détailler plus que ça sans te donner la réponse