Dm de spé maths sur les congruences

[ClemenceV]

Bonjour,
pourriez-vous m'aider pour mon dm je n'y arrive pas.

Merci beaucoup

n désigne un entier qui s'écrit n=10a+b ou a et b sont des entiers naturels.

Critère de divisibilité par13:
a) Montrer que n est divisible par 13 si et seulement si a +4b est divisible par 13.
b) Application (sans calculatrice):
Les nombres 301 et 351 sont-ils multiples de 13 ?
c)Peut-on avoir n inferieur ou égal à a+4b ?
d) En précisant ses conditions d'utilisation, élaborer un programme permettant de conclure et d'afficher les différentes étapes de l'algorithme.
e) Compléter le tableau ci-contre pour n=7 702 695

Divisibilité par 13:
a | b | a+4b

[Pseuda]

Bonsoir,

a) Commence comme ça :
n= 10a+b divisible par 13
ssi 10a +b 0 (13)
ssi -3a+b 0 (13) (car 10 -3 (13))
ssi 4(-3a+b) 0 (13) (à justifier par implications en utilisant le fait que 4 est premier avec 13)
...
tu dois arriver : ssi a+4b 0 (13)

[titine]

n=10a+b
Si n divisible par 13 alors il existe un entier q tél que n=13q
Donc 10a+b=13q
40a+4b=4*13q
39a+a+4b=4*13q
a+4b= 4*13q-39a=13*(4q-3a)
Donc a+4b est divisible par 13

Si a+4b est divisible par 13 alors il existe un entier q tel que a+4b=13q
Donc 10a+40b=130q
10a+b+39b=130q
10a+b=130q-39b=13*(10q-3b)
Donc n=10a+b est divisible par 13.

[Ben314]

Salut.

-3a+b 0 (13)
ssi 4(-3a+b) 0 (13) (à justifier par implications en utilisant le fait que 4 est premier avec 13)

Question (d'ordre pédagogique) : En "Spé-Math" il voient que les inversibles modulo N sont les nombres premiers avec N ?
Ca fait 2 ou 3 fois que je me pose la question pour savoir si, dans un cas tel que cet exo, on peut donner comme justification celle que Pseuda donne ou si on est obligé de dire que l'équivalence, c'est du x4 dans un sens et du x10 dans l'autre (i.e. calculer explicitement l'inverse).

[Pseuda]

Bonjour,

Ils le voient à travers des exercices en rapport avec le théorème de Bézout (qu'ils n'ont pas encore vu à ce stade de l'année), mais les inverses modulo n ne sont pas du tout au programme de TS.

Cela peut se justifier avec la décomposition en nombres premiers (si 13 divise 4(-3a+b), le facteur 13 ne peut provenir que de -3a+b), parce qu'ils n'ont pas encore vu le théorème de Gauss...

Sinon, comme tu dis Ben314, on peut toujours le faire en 2 fois, c'est-à-dire comme a fait titine, mais retranscrit en congruences :
et

[zygomatique]

salut

certes on "parle" des inversibles modulo un premier ... mais bon on est limite

je le fais pour "la culture" et l'analogie dans R ou ab = 1 et traduisent toutes les deux la notion d'inverse (dans un ensemble adéquat bien sur)

j'interdis bien sur l'écriture (qui n'a pas de sens) mais la compatibilité de la relation de congruence avec l'addition et la multiplication suffit à traiter ce qui se fait au lycée ...


si n = 10a + b et m = a + 4b alors n + 3m = 13(a + b)

ce qui suffit à prouver que n est multiple de 13 si et seulement si m est multiple de 13

en utilisant (ce que j'appelle) la propriété fondamentale de l'arithmétique (du moins au lycée) :

si d divise a et b alors d divise toute combinaison linéaire de a et b

et pour en montrer toute la puissance ...

PS1 : les congruences ne sont peut-être pas encore vu aussi à cette époque de l'année

PS2 : j'évite aussi la solution proposée par titine (fort valide bien sur) mais où on voit de nombreux élèves foncer sur la def ("si n est multiple de ... alors il existe k tel que ... puis 'arrêter net parce qu'il n'y a plus/pas d'idée : c'est un confort (psychologique (on a écrit quelque chose qui est vrai)) mais qui n'apporte rien ... tout en ayant l'impression d'avoir fait quelque chose ...)

bien entendu c'est une roue de secours que j'utilise ... quand j'ai épuisé toutes les idées que le génie du cerveau peut produire ... car c'est très proche de la réflexion mécanique ... qui n'est pas la conception que j'ai de l'instruction (horreur il a prononcé le mot instruction !!! )

...

[ClemenceV]

Merci pour vos réponses !