Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale ArithmétiqueTopics traitant de Arithmétique [tout]Lister tous les topics de mathématiques
Niveau terminale
Partager :

Congruences

Posté par
polari56 06-02-21 à 15:10

Bonjour,
Je n'ai aucune piste pour la résolution de l'exercice, à part que je devine qu'il y a un rapport avec les congruences, auriez-vous des pistes de recherche ?
Voici l'énoncé :
Déterminer, s'ils existent, les entiers naturels n tels que le nombre An = (2^(4n+2)+1)/65 soit
a) un nombre entier
b) un nombre premier.
Merci d'avance.

Posté par
Sylvieg Moderateurre : Congruences 06-02-21 à 15:20

Bonjour,
Pour a)
Une piste possible quand on connait les puissances de 2 :
26 = 64 -1 \; [65]

Sinon, il s'agit de trouver quand \; 1 + 24n+2 \; est divisible par 65.
Ce qui revient à \; 1 + 24n+2 \; divisible par 5 et divisible par 13.
On peut donc commencer par chercher a tel que \; 2a \; soit congru à 1 modulo 5.
Puis chercher b tel que \; 2b \; soit congru à 1 modulo 13.

Ce sont des pistes. A voir si ça aboutit. A défaut, ça devrait permettre de trouver une autre direction.

Posté par
polari56re : Congruences 07-02-21 à 11:30

D'après la piste que vous m'avez donné, j'ai trouvé que 2^a est congru à 1 modulo 5 pour tout a = 4k (k entier naturel), et 2^b est congru à 1 modulo 13 pour tout b = 12k.
Je n'ai pas démontré ce que j'ai dis je l'ai juste découvert grâce à un tableau. Suis-je en train d'aboutir ?

Posté par
Sylvieg Moderateurre : Congruences 07-02-21 à 11:49

Tu as trouvé 24 1 [5]
A partir de là, on peut en déduire à quoi est congru le numérateur de An modulo 5.

Ensuite, de 212 1 [13], on peut déduire des choses modulo 13 pour ce même numérateur.
Mais avec plusieurs cas.
Cherche quand le numérateur est congru à 0 modulo 13.

Je ne vais plus être disponible avant 15h environ.
Mais si tu avances, poste ce que tu trouves et d'autres pourront t'aider.

Posté par
mathafou Moderateurre : Congruences 08-02-21 à 14:14

Bonjour,

pas de réponse de polari56 ...

la question a) n'est pas excessivement compliquée
une fois qu'on a "vu" la périodicité des restes modulo 5 , conséquence de 24 1 [5]
ainsi que de même modulo 13,
la périodicité des restes modulo 65 s'en déduit, et la conclusion.

quant à la b) ...
l'essai des quelques premières valeurs des An entiers de la question a) donnera une conjecture qu'il faudra ensuite [tenter de] prouver ...

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 14:23

Tout à fait d'accord

Posté par
FerreSucrere : Congruences 08-02-21 à 18:55

Je tente de réquisitionner le problème (Sylvieg m'en a fait la proposition), je promet rien, j'ai pas fait beaucoup d'arithmétique,

A_n = \dfrac{2^{4n+2}+1}{65}

1. Tel que A_n \in \Z :

Cela veut dire que : 65 | 2^{4n+2}+1

Or,  5 | 65 \text{,  donc :  }5 | 2^{4n+2}+1

On peut conjecturer que , \forall{n} \in \N , 5 | 2^{4n+2}+1
Démonstration:

1 = 1[5] \Leftrightarrow 2² = -1 [5] \Leftrightarrow 2^4 = 1 [5] \Leftrightarrow 2^{4n} = 1 [5] \Leftrightarrow 2^{4n + 2} = 4[5] \Leftrightarrow 2^{4n+2} +1 = 0[5]

donc : \forall{(n,k)} \in \N^2 , 2^{4n+2}+1 = 5k

65 | 5k \Leftrightarrow k = 13q \text{ ,  } q \in \Z

Soit 65 | 2^{4n+2}+1 \Leftrightarrow 2^{4n+2} + 1 = 13q , q \in \N

Je sais que  n = {1 , 4 , 7} fonctionne mais bon

j'ai l'impression de pas avoir beaucoup avancé mdr, je tourne en rond là ? ou j'ai raté quelque chose ^^?

Posté par
FerreSucrere : Congruences 08-02-21 à 19:02

On peut chercher quand 2^{4n+2} = -1 [13] \Leftrightarrow 2^{4n} = 3[13] \Leftrightarrow 2^{4n} = 16[13] \Leftrightarrow 2^n = 2[13]

Mais ensuite ? (je viens de lire vos messages avant mon post , je voulais pas trop me spoil)

Posté par
FerreSucrere : Congruences 08-02-21 à 19:09

Ah je crois que j'ai pas le droit de passer de 2^4n = 16[13] à 2^n = 2[13]....

Posté par
FerreSucrere : Congruences 08-02-21 à 19:10

Dans ma démonstration du dessus je suppose que c'est presque que des implications ducoup ...

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 19:14

Non, tu ne tournes pas en rond puisque tu as démontré que \; 1 + 24n+2 \; est toujours divisible par 5.
Par contre, tu abuses des .
Partir de \; 24 1 [5] \;.
En déduire 2^{4n+2}+1 = 5k sans écrire devant du "k"
car 2^{4n+2}+1 n'est pas égal à 5k pour tout entier k.

Pour 13, utiliser 212 1 [13].
Regarder mes indications du 7 à 11h49.

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 19:14

Messages croisés

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 19:16

Je ne vais plus être disponible.
Mais continue à chercher !

Posté par
carpediemre : Congruences 08-02-21 à 19:27

salut

je n'étais pas intervenu ... zvec les aides de Sylvieg et ne voyant aucune réponse du posteur

FerreSucre : tout comme le pb de la sphère je pense que tu te crées des difficultés par la lourdeur de la rédaction ... qui permet difficilement de voir d'éventuelles erreurs ... de toute sorte ...

j'aurai tout simplement écrit :

2^{4n + 2} + 1 = 4 \times 16^n + 1  (1)

donc 2^{4n + 2} + 1 \equiv 4 \times1^n + 1 \equiv 5 \equiv 0  [5]

de même (1) et l'égalité 16 = 13 + 3 permettent de résoudre "immédiatement" ce qui se passe modulo 13 ...

Posté par
FerreSucrere : Congruences 08-02-21 à 19:27

Oui j'abuse un peu des équivalences, je sais pas trop quand j'ai le droit de les mettre ou non :/, et oui le pour tout k je me suis trompé

2^{12} = 1[13] \Leftrightarrow 2^{4*3n + 2} = 4[13]

je peux en déduire que n = 3q, q un entier naturel ne satisfait pas notre problème, pas très utile je suppose x) fin c'est déjà ça...

Posté par
FerreSucrere : Congruences 08-02-21 à 20:06

Aucune idée là... je veux bien un peu d'aide ^^

Posté par
FerreSucrere : Congruences 08-02-21 à 20:27

2^4 = 1[5]
2^{12} = 1[13]
2^{3(4n+2)} = -1[13]
2^{3(4n+2)} + 1 = 0 [13]

On a :

(q,n) \in \N²
12n+6 = 4q+2
12n -4q = -4
4(3n-q) = -4
3n-q = -1

? Je sais pas si ça peut aider mais bon xD

Posté par
FerreSucrere : Congruences 08-02-21 à 20:33

Je suis bête,

q = 3n+1

Donc les solutions pour que :

A_n \in \N, A_n = \dfrac{2^{4n+2}+1}{65} \Leftrightarrow n = 3q+1, \forall{q} \in \N

Posté par
FerreSucrere : Congruences 08-02-21 à 20:35

Faut y penser au 2^12 = 1[13] xD
L'exo est sympa en tout cas

Posté par
FerreSucrere : Congruences 08-02-21 à 20:49

J'ai une question peut-être bête mais comment justifier que l'on perd aucune solution ? Avec n = 3q+1 ?

En passant de 2^12 = 1[13] à n = 3q+1 ?

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 20:53

Je n'ai pas regardé le détail, car ta manière de présenter les choses est assez embrouillée.
Mais le résultat est bon :
An est entier si et seulement si n est de la forme 3q+1.
Autrement dit si et seulement si le reste de n dans la division euclidienne par 3 est égal à 1.

Pour penser au 212 1[13] , c'est un classique pour nous quand on travaille sur an modulo p.
Regarder les puissances successives de an pour voir une période apparaître ; puis la démontrer.
Ici, quand on arrive à 26 = 64 = 135 - 1,
on passe directement à 212 = (26)2 (-1)2 [13].
( En fait, il y a un théorème qui permet de savoir que 13 étant premier, 213-1 1 [13] )

Posté par
Sylvieg Moderateurre : Congruences 08-02-21 à 20:55

Pour ta question de 20h49 :
Les restes possibles de la division euclidienne de n par 3 sont 0, 1 et 2
Tu as regardé le cas du reste égal à 1.
Il faut regarder aussi les cas 0 et 2.

Posté par
FerreSucrere : Congruences 08-02-21 à 20:57

Comme j'ai fais avant ? En montrant que si n = 3q ça fonctionne pas :

2^{12} = 1[13] \Rightarrow 2^{4*3n + 2} = 4[13]

soir n \neq 3q, q \in \N

2^{12} = 1[13] \Rightarrow 2^{4*(3n + 1)} = 3[13] \Leftrightarrow 2^{4(3n+1)}+1 = 4[13]

Soit n \neq 3q+1, q \in \N

?? Nécessaire ou ?

Posté par
FerreSucrere : Congruences 08-02-21 à 21:00

Ouais j'avoue que c'est pas clair ce que j'ai fais mdr j'avançais à l'aveugle ect... en plus le fait d'être sur téléphone fait que je rédigeais pas beaucoup là cette fois ci x)

Posté par
carpediemre : Congruences 08-02-21 à 21:16

d'après mon précédent post :

4 \times 16^n + 1 \equiv 0 \iff 4 \times 3^n + 1 \equiv 0 \iff_{\red (1)} 3(3^{n - 1} - 1) \equiv 0  \iff_{\red (2)} 3^{n - 1} \equiv 1 [13]

(1) : je multiplie par -3
(2) : je multiplie par 4

Posté par
FerreSucrere : Congruences 08-02-21 à 22:42

Ah ouaiss d'accord je voyais pas trop où tu voulais en venir tout à l'heure désolé ^^, j'avais oublié que j'avais le droit de faire ça ..
Mais une fois rendu à :

3^{n-1} = 1[13]

On en fait quoi ? ^^

Posté par
FerreSucrere : Congruences 08-02-21 à 22:54

Je vois rien du tout

Posté par
FerreSucrere : Congruences 08-02-21 à 22:56

Tu montres que :

3^3 = 1[13]
3^{3q} = 1[13]
3^{3q+1-1} = 1[13]

Et donc que n = 3q+1 ?

Posté par
carpediemre : Congruences 09-02-21 à 08:46

par exemple ...

de toute façon à un moment il faut faire "un tableau de congruence" de k^p modulo 13 pour un certain cas

avec ce que tu as fait c'est k = 2

avec mon cheminement k = 3


et l'avantage avec mon cheminement c'est que ce tableau est quasiment inutile du fait que 3^3 = 1  [13] est immédiat lorsqu'on connait ses tables de multiplication !!

Posté par
Sylvieg Moderateurre : Congruences 09-02-21 à 08:48

Bonjour,
Je laisse carpediem continuer avec sa méthode.
Cependant, je trouve que lui aussi abuse des .
Au niveau terminale, seuls des sont justifiés par (1) et (2).

Je reprends la mienne :
Si n = 3q+1 \; alors \; 1+24n+2 0 [13] (déjà démontré)
Si n = 3q+2 \; alors \; 1+24n+2 = 1+212q+10 1+(212)q210 1+1q1024 1025 [13]
Si n = 3q , je te laisse le traiter.
Conclure que seul le cas n = 3q+1 donne un multiple de 13 pour le numérateur.

Posté par
Sylvieg Moderateurre : Congruences 09-02-21 à 08:52

En fait, on peut ne faire qu'une seule transformation de 1+24n+2 avec n = 3q+r, puis séparer les 3 cas :
n = 3q+r donne \; 1+24n+2 = 1+212q+4r+2 1+(212)q24r+2 1+1q(24)r22 1+ 43r \; [13]
On tombe sur quelque chose qui ressemble à ce qu'a écrit carpediem à 21h16.

Posté par
mathafou Moderateurre : Congruences 09-02-21 à 09:30

Citation :
de toute façon à un moment il faut faire "un tableau de congruence" de k^p modulo 13 pour un certain cas
tu voulais dire un certain k

en effet ce tableau est "presque" obligatoire car ce qu'on cherche surtout c'est la périodicité des restes
c'est à dire le plus petit p tel que k^p ≡ 1 [13]
ainsi le fait de "remarquer" que 64 ≡ -1 [65] conduit à une périodicité de 12 (2^12 ≡ 1 [65] voire même modulo 13)
ce qui ne prouve nullement que 12 est le plus petit !
la seule chose qu'on sait en ayant dit cela c'est que la période (le plus petit p) est un diviseur de 12

pour les 3^p modulo 13 la remarque 3^3 ≡ 1 [13] ne suffit pas, on a dû "essayer" 3^1 et 3^2 (c'est instantané, certes, mais on a dû le faire quand même dans sa tête en une fraction de seconde)

le fait de "réduire" l'étude de 24n à l'étude de 3n est intéressante à ce point de vue là : une période de 3 "coup de bol" au lieu d'une période de 12
mais au final :
écrire que 24n+12k ≡ 4n [13] ou que 3n+3k ≡ 3n [13] quels que soient k et n revient un peu au même :
An+3k est solution si et seulement si An est solution.
et il suffit donc de tester n = 0, 1 et 2 pour conclure sur l'ensemble des solutions.

Posté par
mathafou Moderateurre : Congruences 09-02-21 à 09:33

** "écrire que 24n+12k ≡ 24n [13]" bien entendu ( pataquès dans le placement de la balise sup)

Posté par
carpediemre : Congruences 09-02-21 à 09:57

oui bien sûr : c'est le cas k !!! (et avec 3 ça l'est moins !!)

d'accord pour tout : c'est "quasiment" du pareil au même : la seule différence étant la "quantité" de calculs, manipulations ou vérifications pour trouver la période des restes

Citation :
Le génie c'est 97 % de transpiration, 2 % d'inspiration et 1 % de veine. Jean COCTEAU
la chance sourit aux audacieux ... mais elles ne suffit pas !!!
il y faut de l'effort et de la réflexion !!

Posté par
FerreSucrere : Congruences 09-02-21 à 10:03

D'accord d'accord merci en tout cas

Posté par
Sylvieg Moderateurre : Congruences 09-02-21 à 11:51

Citation :
la chance sourit aux audacieux
Belle maxime
Autrement dit :
Qui ne tente rien ne trouve rien !
Il faut se lancer, essayer, écrire des choses.
Si ça marche, tant mieux.
Si ça ne marche pas, on y voit un peu plus clair et souvent une autre idée apparaît.
Si on est toujours dans le brouillard, on tente autre chose.
Quand on finit par trouver une démarche qui aboutit, on fait un bilan clair pour éviter de passer à côté de simplifications éventuelles.

Et la seconde question

Posté par
carpediemre : Congruences 10-02-21 à 14:07

Sylvieg @ 09-02-2021 à 11:51

Citation :
la chance sourit aux audacieux
Belle maxime
Autrement dit :
Qui ne tente rien ne trouve rien !
Il faut se lancer, essayer, écrire des choses.
Si ça marche, tant mieux.
Si ça ne marche pas, on y voit un peu plus clair et souvent une autre idée apparaît.
Si on est toujours dans le brouillard, on tente autre chose.
Quand on finit par trouver une démarche qui aboutit, on fait un bilan clair pour éviter de passer à côté de simplifications éventuelles.
tout à fait d'accord !

Sylvieg @ 09-02-2021 à 11:51

Et la seconde question
une idée

a_n = 2^{4n + 2} + 1 est multiple de 65 si n = 3k + 1

donc je remplace n par 3n + 1 :

a_n = 2^{12n + 6} + 1 = 65 \times 2^{12n} - (2^{12n} - 1)

b_n = 2^{12n} - 1 = (2^n - 1)(2^{2n} + 2^n + 1)(2^n + 1)(2^{2n} - 2^n + 1)(2^{2n} +1)(2^{4n} - 2^{2n} + 1)

je regarde alors quel facteur est multiple de 5 et quel facteur est multiple de 13 et je "détermine" le quotient

bon après déterminer quand une différence de deux entiers est première c'est pas gagné non plus !!!

mais pour l'instant je ne vois guère mieux ... et je ne pense pas que cette idée soit ... pertinente !!

Posté par
FerreSucrere : Congruences 10-02-21 à 14:15

la question b) est impossible non ? si on trouvait n = ... ça veut dire qu'on aurait une fonction qui donnerait que des nombres premiers ? La réponse doit contenir un nombre premier genre n = 2(p-3) Avec p premier (exemple) ?
Faut utiliser des propriétés je suppose qui font référence aux nombres premiers non ?

Posté par
carpediemre : Congruences 10-02-21 à 14:36

non pas forcément que des nombres premiers mais parfois des nombres premiers !!

Posté par
mathafou Moderateurre : Congruences 10-02-21 à 16:03

moi j'ai ça (programme Python)

A[1] = 1

A[4] = 4033
= 37 x 109

A[7] = 16519105
= 5 x 41 x 61 x 1321

A[10] = 67662254017
= 29 x 113 x 1429 x etc

A[13] = 277144592453569
= 37 x 109 x etc

A[16] = 1135184250689818561
= 397 x 2113 x etc

A[19] = 4649714690825496825793
= 13 x 53 x 157 x 313 x 1249 x 1613 x 3121 x etc

A[22] = 19045231373621234998448065
= 5 x 37 x 41 x 61 x 109 x 181 x 1321 x etc

A[25] = 78009267706352578553643274177
= 137 x 409 x 953 x 3061 x etc


etc ...
(le programme Python ne cherche que les diviseurs premiers < 10000 ,
on obtient des facteurs premier à des dizaines de chiffres si on factorise "en vrai" (ils sont pudiquement caché dans le "× etc"

par exemple :
A73 = un nombre à 87 chiffres = 29 × 113 × 197 × 1429 × 14449 × 540961 × 19707683773 × 4 981857697937 × 40544859693521152369 × 17059410504738323992180849
le dernier facteur premier de 26 chiffres

je suis allé ainsi jusqu'à A148 = un nombre de 178 chiffre, divisible par 37
(c'est très rapide, mais la liste longue comme dix bras obtenue, n'incite pas à continuer)

bref la conjecture qui est au départ :
"premiers pour certaines valeurs de n" (et pas d'autres, donc parfois premier, parfois non)
deviendrait plutôt
"n'est jamais premier"

quant à le démontrer, au vu des diviseurs de An un peu erratiques observés, c'est pas gagné !

Posté par
carpediemre : Congruences 10-02-21 à 16:26

ouais ...

quelques info pour éclairer :

nombres de Fermat :

Posté par
mathafou Moderateurre : Congruences 10-02-21 à 16:30

oui, celui qui démontrera que F_n = 2^{2^n}+1 est composé pour toutes les valeurs de n ≥ 5 aura la médaille Field ...

Posté par
Sylvieg Moderateurre : Congruences 10-02-21 à 16:54

Un coup de pouce :
1+q3 = (1+q)(1-q+q2)

Posté par
mathafou Moderateurre : Congruences 10-02-21 à 17:30

oui, ça marche !

Posté par
carpediemre : Congruences 10-02-21 à 18:07

qu'est-ce qui marche ?

Posté par
mathafou Moderateurre : Congruences 10-02-21 à 18:19

la démonstration que pour tout n > un certain rang An quand il est entier est composé... pardi.

il n'y a qu'a trouver de quel "q" il est question dans 2^{12k+6} + 1 ...
et de s'assurer que chacun des facteurs est > 1 après division du produit par 65 ...

et vérifier individuellement que c'est déja vrai pour n ≤ le "certain rang"
(d'ailleurs très petit)

Posté par
carpediemre : Congruences 11-02-21 à 09:48

oui que j'ai fait inutilement compliqué !!!

4 * (3n + 1) + 2 a le bon goût d'être égal à 3 * (4n + 2) ...


Rechercher
Menu
Espace membre
Changer d'île

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 1675 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 !