TS- Nombres premiers

[inviteea5db5e2]

Bonjour,

J'ai un petit problème avec un exo de spé, comme à chaque début de chapitre. On me demande ici de déterminer les restes possible de la division d'un nombre premier p par 12.

Très intuitivment j'aurais répondu tous les nombres premiers compris entre 0 et 11, en incluant 1. Donc, 1;2;3;5;7;11.

Mais il doit surement y avoir une raison mathématique à celà, et je vois pas. Pour info, je n'ai pas encore vu les congruences. On a fait que les divisions euclidiennes et les multiples : mes connaissances s'arrêtent à a = b q ou a = b q + r.

Comment est ce que je peux montrer ma réponse avec ca ? à supposer que ma réponse soit juste...

Merci d'avance.
-----

[invitebfd92313]

tu l'as dit toi même, tu sais que p=12q+r, et tu veux savoir les valeurs possibles de r. Raisonne a l'envers. Lesquels sont possibles ?, par exemple, si r=2 : p=12q+2. Que remarques-tu ? Qu'en conclus-tu ?

[inviteea5db5e2]

Si r=2, on a p = 12 q +2 = 2 ( 6q + 1 ) et p n'est pas premier, puisque divisible par 2. Donc 2 apparaît comme un reste impossible.

Mais Achtung ! Si p = 2 ( p est bien premier ) La division euclidienne s'écrit
p = 12 x 0 + 2 et 2 est un reste possible.

Comprennez-vous mon embarras ?

[invitebb921944]

Si r=2, on a p = 12 q +2 = 2 ( 6q + 1 ) et p n'est pas premier, puisque divisible par 2. Donc 2 apparaît comme un reste impossible.

Ah, et si q vaut 0, p n'est pas premier ?

[A voir en vidéo sur Futura]

[inviteea5db5e2]

Bien sûr que si !

Qui a dit le contraire ? Pas moi en tout cas...

( Merci Ganash, j'avais ouvert qu'un oeil )

[invite2220c077]

Revenons à la racine des choses.

Dire qu'un nombre b divise a <=> il existe deux entiers q et r avec 0 <= r < b vérifiant :

a = bq + r.

Ici nous devons trouver tous les entier r (0<= r < 12) vérifiant :

p = 12q + r.

Nous savons que p est un nombre premier <=> p est un nombre impair (hormis le cas p = 2). Ainsi on a : p = 12k + 1 ou p = 12k + 3 ou p = 12k + 5 .... ou p = 12k + 11.

Ainsi les différents restes sont : r = {1, 3, 5, 7, 9, 11}

Maintenant lorsque p = 2, alors le seul reste possible est 2 : 2 = 12*0 + 2.

Donc r = {1, 2, 3, 5, 7, 9, 11}

[inviteea5db5e2]

Je vois mal l'équivalence entre p premier et p impair...

Mais sinon je suis ton raisonnement -Zweig-

[invitebb921944]

Très intuitivment j'aurais répondu tous les nombres premiers compris entre 0 et 11, en incluant 1. Donc, 1;2;3;5;7;11.

Soit p un nombre premier.
On fait la division euclidienne :
p=12q+r

Est-ce que 12q est premier ?
Si r est divisible par autre chose que 1 ou r, que peut-on en conclure sur p ?

Tu peux maintenant trouver les valeurs de r possibles...

[invite2220c077]

"Dire qu'un nombre b divise a <=> il existe deux entiers q et r avec 0 <= r < b vérifiant :"

Je voulais plutôt dire "Soient a et b deux entiers. Il existe deux entiers q et r, avec 0<= r < b, vérifiant :

a = bq + r

MS.11 > Bah tous les nombres premiers sont impairs ... hormis 2 ... En fait ce n'était pas une équivalence mais une implication pardon !

[invitebb921944]

Nous savons que p est un nombre premier <=> p est un nombre impair

C'est une implication.
9 est impair et non premier.

[invitebb921944]

Tiens ce que j'ai dit ne marche pas oublie ma méthode.

[invite2220c077]

Oui je l'ai précisé plus haut, mais après 5min on ne peut plus rectifier son msg ...

[invitebfd92313]

ms.11 tu avais bien compris ou je voulais en venir, et la remarque que tu as faite s'applique aussi pour r=3 : p=12q+3=3(4q+1), donc p est divisible par 3, donc p n'est pas premier (contradiction). Evidemment, de meme que pour le cas r=2, si q=0 le fait que p soit divisible par 3 n'est pas gênant puisque p=3.
Donc pour généraliser, si on sépare le cas q=0 et le cas q>0 (ce qui je pense est le but de l'exercice sinon l'intérêt serait a mon avis limité), il faut raisonner sur les diviseurs de 12.

[inviteea5db5e2]

Je crois que ca y est ! J'en suis pas sûr mais bon :

p est premier donc ses diviseurs sont 1 et p.
La division euclidienne de p par 12 s'écrit : p = 12 q + r
12 q est divisible par 12 même si q=0. Il est aussi divisible par tous les diviseurs de 12. Donc pour que p soit premier il faut que r soit premier aussi.
Or r doit être compris entre 11 et 0 inclus.

On en déduit que l'ensemble des restes possibles est : 1 ; 2 ; 3 ; 5 ; 7 ; 11. Soit les nombres premiers strictement inférieurs à 12 en ajoitant 1.

En raisonnant par l'absurde si r n'avait pas été premier 12 q + r aurait admis des diviseurs et p n'aurait pas pu être premier.

[invite2220c077]

il faut que r soit premier aussi.

Pas vraiment. Les conditions que doit satisfaire r sont :

- 0 <= r < 12

- ne doit pas être un diviseur de 12, car dans ce cas-là le membre de droite se factorise, et cela contredit la définition même d'un nombre premier.

- ne doit pas être pair (hormis pour le cas particulier où p = 2), car sinon on aurait 12q + r = nombre pair, ce qui contredit une fois de plus la définition d'un nombre premier.

[invitebfd92313]

ton raisonnement est faux, en effet si j'applique la même démarche pour les restes possibles de 16, je peux dire :
16 n'est pas premier, donc pour que 16q+r soit premier, il faut que r soit premier.
Or, cette assertion est fausse puisque 2*16+15=47 est premier alors que 15 n'est pas premier. par contre tu remarqueras que 15 ne divise pas 16 (à bon entendeur ^^)

edit : chassé croisé. Par contre "il ne doit pas être pair" est compris dans "il ne doit pas diviser 12", non ?

[inviteea5db5e2]

ton raisonnement est faux, en effet si j'applique la même démarche pour les restes possibles de 16, je peux dire :
16 n'est pas premier, donc pour que 16q+r soit premier, il faut que r soit premier.
Or, cette assertion est fausse puisque 2*16+15=47 est premier alors que 15 n'est pas premier. par contre tu remarqueras que 15 ne divise pas 16 (à bon entendeur ^^)

edit : chassé croisé. Par contre "il ne doit pas être pair" est compris dans "il ne doit pas diviser 12", non ?

Il faut que le reste ne divise pas 12 dans mon cas.

Mais ton contre exemple n'est pas valable. Tu as montré qu'il n'était pas nécessaire que le reste soit premier . Mais tu n'as pas montré que si le reste est premier mon raisonnement est faux. Enfin je crois pas... Il nous faudrait un logicien pour en débattre clairement là... Mais bon.

Mais en conclusion :

Mon reste :
Je distingue ensuite les cas où p=0 et p>0 pour montrer en factorisant que certains restes m'amèneraient à p pair. C'est bien çà ?

Par exemple si r=4 p n'est pas premier

(puisque égal ou multiple de 4)

Là en l'occurrence je n'aurai pas à distinguer les cas.

[invitebfd92313]

c'est ca, et mon contre-exemple visait a montrer que ton assertion "si n (en l'occurence 12) n'est pas premier, alors il faut que r soit premier pour que p=nq+r soit premier". Vu que j'ai trouvé un n et r non premiers vérifiant nq+r premier, mon contre-exemple est valable. Et vu que ton assetion est fausse, ton raisonnement est faux.

[inviteea5db5e2]

Je suis pas sûr d'avoir compris si la logique des assertions, des implications et des équivalences... Mais j'ai compris comment trouver mes restes !

Et c'était pour ça que je suis venu !

Victoire ! et merci à vous !