Arithmétiques - Congruence/Récurrence

[pikmin]

Bonjour,

Je dois démontrer par récurrence et par congruence qu'un nombre est divisible par un autre.

Je dois d'abord le faire avec et 19, puis avec et 3.

Avec ces nombres j'y arrive sans problème, par contre je n'arrive pas à démontrer que est divisible par 13.

J'ai =

Mais je n'arrive pas à continuer, comme je l'avais fait dans les autres en factorisant par un multiple de 13 :hum:

[lapras]

salut
remarque que modulo 13

donc

or

donc

Pas besoin de récurrence !

[_-Gaara-_]

Salut,

tu as 10^6 = 1 [13]

et 3^3 = 1 [13]


=)

[leon1789]

Pas besoin de récurrence !

Oui effectivement... et en plus, c'est pareil pour les deux autres cas :

donc

, , , donc

[pikmin]

oui je sais bien qu'on peut le faire avec les congruences, je l'avais d'ailleurs déjà fait. Mais on est obligé d'utiliser les deux méthodes (congruence ET récurrence)

Et c'est juste le dernier qui me pose problème avec les récurrences

[leon1789]

Comme le dit Gaara, donc 13 divise .
Idem pour .
Donc une récurrence est faisable.

[pikmin]

et comme je l'ai dit, on ne doit pas du tout utiliser les congruences dans la démonstration par récurrence.

[nonam]

Bonjour,

Grace à l'hypothèse de récurrence et au fait que 13 divise , tu obtiens l'hérédité. La seule congruence utilisée est , mais je ne crois pas qu'il soit possible de faire sans...

[pikmin]

Merci nonam, je verrais avec ça :happy2:

[lapras]

pour le 10^6 = 3^3 [13] c'est évident en remarquant que :
3^3 = 27 = 1 [13]
10=-3[13]
10^6=3^6=1[13]
Je ne vois pas l'utilité de faire de la récurrence pour faire de la récurrence...

[nonam]

moi non plus, mais puisque l'énoncé de l'exercice est comme ça, il faut bien s'adapter...

[leon1789]

et comme je l'ai dit, on ne doit pas du tout utiliser les congruences dans la démonstration par récurrence.

Fallait-il encore comprendre que le mot "modulo" est interdit dans la récurrence !
Et puis c'est trop difficile pour toi d'écrire sur ta feuille > quand tu lis sur le forum > ??? A moins que tu n'aies pas le droit d'utiliser la division non plus... mdr...

Je ne vois pas l'utilité de faire de la récurrence pour faire de la récurrence...

C'est un exo imposant la récurrence, donc il faut se plier ...

moi non plus, mais puisque l'énoncé de l'exercice est comme ça, il faut bien s'adapter...

oui, mais peut-être que l'objectif pédagogique est-il justement de montrer l'efficacité du calcul modulaire.

[leon1789]

La seule congruence utilisée est , mais je ne crois pas qu'il soit possible de faire sans...

je propose un truc un poil plus simple, factoriser .

Avec ces nombres j'y arrive sans problème, par contre je n'arrive pas à démontrer que est divisible par 13.

D'abord, je pense qu'il faut écrire

pour n=0 : 13 divise , trivial.

hérédité : on suppose que est divisible par 13.
On écrit avec
Or divisble par 13
et et divisible par 13 (factorisation classique quand on fait des preuves par 1001... ce qui est assez rare, j'en conviens :we: )
donc est divisible par 13
Comme est divisible par 13, aussi.

C'était exactement ce qu'on te proposait... en écrivant 13 divise à la place de !!!! :marteau: :marteau: :marteau: :marteau: :marteau: :marteau: :marteau: :marteau:

[leon1789]

Le truc habituel et amusant est de demander de prouver par récurrence que 13 divise pour tout n.
Et ceux qui oublient l'initialisation de la récurrence vont y arriver :ptdr:

[nonam]

à oui, jolie ta démo de : 13 divise :jap: ...
comme quoi on peut faire de grandes choses avec peu d'outils :we: !

[pikmin]

pas de ma faute si l'énoncé est comme ça :hum: avec les congruences c'est 10 fois plus simple, mais bon, y'a un énoncé faut s'y plier

[leon1789]

à oui, jolie ta démo de : 13 divise :jap:

ou ?? :++:

pas de ma faute si l'énoncé est comme ça :hum: avec les congruences c'est 10 fois plus simple, mais bon, y'a un énoncé faut s'y plier

oui, mais ce n'est pas compliqué de déguiser une démo "modulaire" en une récurrence. Ca te va ainsi ??