Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Congruences, diviseurs, nombres premiers ( type bac )

Posté par
Masquerade
30-04-13 à 16:44

Bonjour,
Je fais un sujet d'arithmétique type bac et j'aurai besoin de votre aide pour faire les dernières questions.
Voilà l'énoncé ( c'est un peu long ) :

Pour tout entier naturel n 2 , on pose A(n) = n4 + 1 .

1a) Etudier la parité de l'entier A(n).
1b) Montrer que A(n) n'est pas multiple de 3.
1c) Montrer que tout entier d diviseur de A(n) est premier avec n.
1d) Montrer que, pour tout entier d diviseur de A(n) , on a  n8 1 (mod d) .


Soit d un diviseur de A(n). On pose s le plus petit des entiers naturels non nuls k tels que nk 1 (mod d).

2a) Soit k un tel entier. En utilisant la division euclidienne de k par s, montrer que s divise k.
2b) En déduire que s est un diviseur de 8.
2c) Montrer que si, de plus, d est premier, alors s est un diviseur de d-1.

3) Dans cette question, on suppose que n est pair.
Soit p un diviseur premier de A(n). En examinant successivement les cas s=1, s=2, s=4, conclure que  p 1 (mod 8) .

4) Appliquer ce qui précède à la recherche des diviseurs premiers de A(12).
Annexe : La liste des nombres premiers congrus à 1 modulo 8 commence par : 17 , 41 , 73 , 89 , 113 , 137 , ...



J'ai réussi à faire toutes les questions ( je vous expose le raisonnement si vous le souhaiter ) sauf les 3) et 4).
Je n'arrive pas à partir dans la question 3), avoir une idée du raisonnement. Les valeurs proposées de s sont bien celles possibles car s divise 8, il est dit de faire une disjonction des cas, mais je ne sais pas quoi faire.
Pour la 4), les nombres proposés en annexe sont potentiellement diviseurs de A(12) = 20737, ( en fait, le solutions sont 89 et 233 ), mais comment expliciter une démarche ?

Merci d'avance à ceux qui pourront m'aider.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 18:04

Tout d'abord p ne peut pas être 2.
Car n est pair et donc A(n) est impair et donc 2 ne le divise pas.

(quand p=2 on a 1\equiv -1 \mod{2})


p divise A(n) est équivalent à:


n^4 \equiv -1 \mod{p}

si s=1 alors n\equiv 1 \mod{p} ce qui veut dire que n^4\equiv 1 \mod{p}

donc s ne peut pas être 1



si s=2 alors n^2\equiv 1 \mod{p} ce qui veut dire que n^4\equiv 1 \mod{p}

donc s ne peut pas être 2

s=4 est exclus.

Donc s=8


d'après 2c) 8 divise p-1

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 18:14

un nombre entier n a un diviseur inférieur ou égal à \sqrt n

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 18:15

Le résultat marche aussi si on remplace "diviseur" par "diviseur premier"

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 18:23

Dans ce dernier cas, il faut évidemment que n ne soit pas premier.

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 18:27

Bonjour FDP et Masquerade,
Si j'ai bien compris, comme p 2 et n^4 \equiv -1 \mod{p}
on ne peut pas avoir n^4 \equiv 1 \mod{p}

Par ailleurs, si s=1 ou s=2 ou s=4 alors n^4 \equiv 1 \mod{p} .
s ne prend donc aucune de ces trois valeurs, et comme s divise 8 , il ne reste que la possibilité s=8 .

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:01

Merci beaucoup FDP, j'ai tout compris grâce à toi (:

Je pense avoir une idée pour la 4) :

Selon la question 3), les diviseurs premiers de A(12) = 20737 sont tous congrus à 1 modulo 8.

Il faut donc rechercher tout les entiers premiers congrus à 1 modulo 8 : parmis eux, certains sont les diviseurs premiers de A(12).

Ces derniers apparaissent doncdans la décomposition primaire de A(12) = 20737 .

Pour dresser la liste exhaustive des diviseurs premiers de A(12), il faut donc :

* Dresser une table des entiers premiers congrus à 1 modulo 8
* Prendre le premier nombre de cette table, et vérifier si il divise A(12)
* Si oui, alors nommons le p1
* Si non, alors recommencer l'étape 2) avec le deuxième nombre de cette table ( puis le troisième, le quatrième, ..., si l'on doit réitérer l'opération )
* Prendre le nombre suivant p1 dans la table et vérifier si il divise A(12)
* Si oui, alors nommons le p2 . Calculer p1x p2 . Le comparer à A(12) en vérifiant par tâtonnement si aucun couple d'entiers naturels (1 , 2) ne permet de trouver p11 x p22 = A(12) . Si oui, alors on a trouver tous les diviseurs premiers de A(12) car on a trouvé sa décomposition primaire . Si non, alors recommencer l'étape 5) avec le nombre suivant p2 , puis p3 , ...
* Si non, alors recommencer l'étape 5) avec le nombre suivant p1 deux crans plus loin dans la table, puis trois crans plus loin ,...


On applique cette méthode, puis l'on déduit que les diviseurs premiers de A(12) sont 89 et 233.

Une autre idée plus simple ?

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:07

Bonjour,

Ce que tu propose FDP ( tu l'a publié en même temps que j'écrivais mon message ) , ce n'est pas suffisant, cela permet seulement de prouver l'existence de tels nombres premiers, mais pas de les calculer.

D'autre part, A(12) 144 et 233 divise A(12), donc on ne peut pas limiter l'étude aux nombres premiers entre 1 et A(12) .

Tu as très bien compris que ce disais FDP, Sylvieg (: C'est ce qu'on appele une " disjonction des cas " .

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:09

20737 144
Si 20737 n'est pas premier, on est certain de trouver un diviseur dans la liste donnée en annexe.

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:15

Nous nous sommes croisés.
Si 233 n'était pas premier, il aurait un diviseur inférieur à 233 ... qui diviserait 20737.
Donc 233 est premier.

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:23

Je comprends bien, mais cela ne répond pas à la question 4). Comment faîtes-vous ?

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:30

J'utilise l'annexe :
Je regarde successivement si 17 , 41 , 73 , 89 , 113 , 137 divisent 20737 en sachant que je n'aurai pas à aller plus loin.
Je m'arrête à 89 avec 20737 = 89233 . Et je sais que 233 est premier aussi.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:31

Masquerade:

Si n est un nombre composé alors il a un diviseur premier qui est inférieur ou égal à \sqrt n

Mais cela ne veut pas dire que tous les diviseurs premiers de n sont inférieurs ou égaux à
\sqrt n

\sqrt {A(12)} < 144

et tu vas trouver que le seul nombre premier p inférieur à 144 qui divise A(12)) est  89
Mais le travail n'est pas fini il faut considérer le nombre entier \dfrac{A(12)}{89} qui est 233.
Il faut vérifier que 233 n'est pas composé.
Il suffit de tester tous les diviseurs premier de la liste compris entre \sqrt {A(12)} et
\sqrt 233 puisque 233 n'est pas une puissance de 89

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:35

La liste dont je parle est celle des diviseurs premiers qui sont congrus à 8 modulo 1

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:42

j'ai écrit une ânerie.

\sqrt{233} < 144 et 233 n'est pas une puissance de 89 donc 233 est premier.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 19:44

un diviseur de 233 est aussi un diviseur de A(12) il est donc congru à 1 modulo 8 lui aussi.

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 20:04

Je vois ce que tu veut dire FDP, je peux essayer d'écrire cela pour résumer :

Selon la question 3) , puisque 12 est pair, tous les diviseurs premiers de A(12) sont congrus à 1 modulo 8 .

On teste les premiers nombres de la table des nombres premiers congrus à 1 modulo 8 : 17, 41, 73 ne divisent pas A(12) , mais 89 le divise.

A(12) / 89 = 233 .

Ainsi, deux figures possibles : ou tous les autres diviseurs premiers de A(12) forment un produit égal à 233 , ou 233 est premier.

On vérifie que 233 est premier en testant sa divisibilité par i où 2 i 233  

On trouve que 233 est premier.

( N.B. On en déduit que 233 1 (mod 8) )

On vérifie que 89 x 233 = 20737 = A(12) .

Les diviseurs premiers de A(12) sont : 89 et 233 .


Tu es d'accord ?

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 20:40

Je me mêle un peu de ce qui me regarde pas mais il est inutile de vérifier que 233 est premier.
S'il ne l'était pas, il aurait un diviseur inférieur à 233 donc à 16 ; ce diviseur serait un diviseur de 20737 alors que le plus petit diviseur de 20737 est 89 .

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:21

Ce que l'on peut prouver, c'est que 89 est le plus petit entier premier qui divise A(12) et qui est congru à 1 modulo 8.

Cependant, même si je suis d'accord que c'est le plus petit entier ( sans condition sur sa primalité ) strictement supérieur à 1 qui divise A(12), comment le démontrer ?

Posté par
Sylvieg Moderateur
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:25

Citation :
Soit p un diviseur premier de A(n). En examinant successivement les cas s=1, s=2, s=4, conclure que p 1 (mod 8) .

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:33

J'ai en partie l'idée.

Supposons que 89 soit le plus petit entier premier qui divise A(12).

Puisque l'on sait que le plus petit diviseur d'un nombre est premier, on en conclue que 89 est le plus petit entier qui divise A(12).

On finit comme tu l'as dit :

Donc si 233 est composé, alors il possède un diviseur plus petit que 233 , donc plus petit que 15 .
Ce diviseur est alors aussi diviseur de A(12) et plus petit que 89.
Contradiction, donc 233 est premier.

Maintenant, il faut démontrer que 89 est le plus petit entier premier qui divise A(12).
Car ce que l'on sait, c'est que 89 est le plus petit entier premier qui divise A(12) et qui est congru à 1 modulo 8.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:34

Masquerade :

Pour tester les diviseurs premiers  congrus à 1 modulo 8 il faut bien s'arrêter à un moment donné.
C'est là où intervient la racine carrée de A(12) qui est à peu près 144.

Tu vas t'arrêter où autrement? Jusqu'à ce que p soit plus grand que A(12)?
Cela fait beaucoup de candidats possibles.

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:36

Et je comprends ton message Sylvieg :

Tout les diviseurs premiers de A(12) sont congru à 1 modulo 8, donc puisque
89 est le plus petit entier premier qui divise A(12) et qui est congru à 1 modulo 8,
on en déduit que 89 est le plus petit entier premier qui divise A(12).

Merci, grâce à vous, j'ai fini mon exercice ! (:

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:38

Masquerade:

Si 233 a un diviseur premier celui-ci est congru à 1 modulo 8 puisque 233 divise A(12)

Par ailleurs, si 233 n'est pas premier il a diviseur premier qui est inférieur à 15 mais ce n'est pas possible puisqu'on sait qu'aucun nombre premier congru à 1 modulo inférieurs à 144 ne divisent 233 hormis 89.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:41

J'ai mal rédigé:

Si 233 a un diviseur premier celui-ci est congru à 1 modulo 8 puisque 233 divise A(12)

Par ailleurs, si 233 n'est pas premier il a diviseur premier qui est inférieur à 15 mais ce n'est pas possible puisqu'on sait qu'aucun nombre premier congru à 1 modulo 8 inférieurs à 144 ne divisent A(12) hormis 89.

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:41

FDP :

Je comprends ce que tu dis :

On étudie les diviseurs premiers entre 1 et A(12) , puis on en déduie les autres diviseurs. Dès lors, plus besoin d'étudier les diviseurs premiers entre 1 et A(12) .

Merci !

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:43

Seulement les diviseurs premiers qui sont congrus à 1 modulo 8

Posté par
Masquerade
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:46

Exact, j'ai oublié de le préciser.

Posté par
FDP
re : Congruences, diviseurs, nombres premiers ( type bac ) 30-04-13 à 21:47

en aparté:

Si n=pq alors p ou q est inférieur ou égal à \sqrt n

Pourquoi?

Parce que si c'était faux cela signifie qu'on aurait p>\sqrt n et q>\sqrt n

et donc en multipliant ces deux inégalités:

pq>n ce qui est absurde puisque n=pq



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1561 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !