Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 21-06-2011 20:54:13

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premiers modulo 12 : éttape 2

Soit a un nombre divisant un entier égal à 4k²+3 avec k>0 non divisible par 3, montrer que ce nombre et son codiviseur sont égaux à 1 modulo 3.


Ma démarche (gros indices) :
Spoiler : [Afficher le message] Après avoir montré que le diviseur et le codiviseur ont même classe modulo 3, pensez à regarder le diviseur et le codiviseur modulo 12 puis de raisonner par l'absurde sur le diviseur moins sa classe multiplié par le codiviseur moins sa classe, de réinjecter les résultats obtenus par les modulo 12.
Finalement réduire modulo 3.



Annonces sponsorisées :

Un mathématicien complet est topologiquement fermé!
  • |
  • Répondre

#0 Pub

 #2 - 21-06-2011 22:05:32

Memento
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 176

Premieers modulo 12 : étape 2

J'ai un petit problème, je trouve que le diviseur et son codiviseur sont congruent à 1 mod 3 mais aussi 2 mod 3.
Exemple:
55=12*4+7
Or 5 divise 55, 55=5*11, 5 et 11 sont congruent à 2 mod 3.

 #3 - 21-06-2011 23:18:06

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Premies modulo 12 : étape 2

Là je ne comprend plus car 5*11 = 55 = 12*4 + 7 mais 5 = 11 = 2 modulo 3

Peut être le problème complet avec la contrainte a*b = 4k²+3 empêche que a soit égale à 5 modulo 12 et b à 11 modulo 12. Je vais y réfléchir.

 #4 - 22-06-2011 02:04:05

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premiers modulo 12 : étappe 2

J'avais en découpant le problème oublié une hypothèse, merci à Memento  et à  w9Lyl6n. smile


Un mathématicien complet est topologiquement fermé!

 #5 - 22-06-2011 10:10:43

esereth
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 175

peemiers modulo 12 : étape 2

Jouons avec les congruences

Puisque [latex]3[/latex] ne divise pas [latex]k[/latex], [latex]k \equiv 1[/latex] ou [latex]k \equiv -1[/latex] modulo  [latex]\3[/latex] ce qui entraine [latex]k^2 \equiv 1[/latex]  modulo 3 puis [latex]4k^2+3 \equiv 1 [/latex] modulo 3. ( [latex]1\times1+0[/latex])

La table de multiplication modulo 3 ne donne 1 pour résultat du produit que si les deux facteurs sont congrus à 1 modulo 3 .

Donc l'égalité  [latex]4k^2+3=a \times b[/latex], ne peut être réalisée qu'avec [latex]a\equiv 1[/latex] et [latex]b\equiv 1[/latex] modulo 3.

 #6 - 22-06-2011 10:13:52

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premmiers modulo 12 : étape 2

Esereth tu te trompes je crois, vérifie ta table 4=1...


Un mathématicien complet est topologiquement fermé!

 #7 - 22-06-2011 10:34:35

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Premiers modulo 12 : éttape 2

Etape 2 :

Soit a un diviseur de [latex]4k^2+3[/latex]. Le codiviseur est, je suppose, b tel que [latex]ab=4k^2+3[/latex] ?

A ce moment, [latex]4k^2+3[/latex] étant congru à 1 modulo 3, a et b sont soit tous les deux congrus à 1 modulo 3, soit tous les deux congros à 2 modulo 3.

Modulo 12, qu'est-ce que ça donne, sachant que le produit des deux doit être congru à 7 (donc, pas de modulo pair possible) ? Ca donne deux paires de modulos possibles : [latex](1;7)[/latex] dans le cas de la congruence à 1 modulo 3 ; [latex](5;11)[/latex] dans le cas de la congruence à 2 modulo 3.

On va donc essayer de voir que quelque chose cloche dans le cas [latex](5;11)[/latex]. Et là, même avec l'indice... Ca bloque. Je ne comprends pas trop où tu veux en venir, et ça m'embrouille lol


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #8 - 24-06-2011 09:24:06

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Preemiers modulo 12 : étape 2

Désolé pour cet indice minable: une erreur de calcul...
Au secours!


Un mathématicien complet est topologiquement fermé!

 #9 - 24-06-2011 11:36:37

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

premiers mosulo 12 : étape 2

Je me disais aussi que ça pouvait pas être aussi dur smile

 #10 - 28-06-2011 08:19:40

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

Premiers modluo 12 : étape 2

Bon, j'ai un peu creusé le sujet
Si 4k^2+3 = p.q avec p%12 = 5 et q%12 = 11, alors p=12x+5 et q=12y+11

On va essayer de procéder par récurrence pour démontrer que si un nombre peut s'écrire sous la forme 4k^2+3, alors il n'est multiple d'aucun 12n+5 ni 12n+11

Petit résultat préliminaire : en analysant la table des produits modulo 12, on remarque que :
- si x est congru à 5 modulo 12 et est composé, alors un de ses diviseurs est congru à 5 ou à 11 modulo 12 (en effet, seuls 1*5 et 7*11 mod 12 donnent 5)
- si x est congru à 11 modulo 12 et est composé, alors un de ses diviseurs est congru à 5 ou à 11 modulo 12 (en effet, seuls 1*11 et 7*5 mod 12 donnent 11)


Pour n = 1 :

* si 4k^2+3 = 5.q, alors 4k^2+3 % 5 = 0
donc 4k^2 = 2 + 5a.
Du coup, a%4 = 2 et on peut alors écrire 4k^2 = 12 + 20a'; d'où k^2 = 3 mod 5; qui n'admet pas de solution

* si 4k^2+3 = 11.p, alors 4k^2+3 % 11 = 0
donc 4k^2 = 8 + 11a.
Du coup, a%4 = 0 et on peut alors écrire k^2 = 2 mod 11; qui n'admet pas de solution

Ca, c'était plutôt facile. Maintenant, supposons que pour tout i inférieur à n, 12i+5 et 12i+11 ne peuvent être des facteurs de 4k^2+3

Au rang n:

* Pour 12n+5, on va distinguer 2 cas:
- soit ce nombre est composé, d'après notre résultat préliminaire il est facteur de 12i+5 ou de 12i+11 avec i<n. Dans ce cas, on a déjà traité du fait que 4k^2+3 ne peut être un multiple de 12i+5 ou 12i+11 dans notre récurrence
- soit ce nombre est premier: dans ce cas, 4k^2+3 = 0 mod [12n+5] donc
4k^2 = 36n + 12 [12n+5]
k^2 = 9n+3[12n+5]

* Pour 12n+11, on va aussi distinguer 2 cas:

- soit ce nombre est composé, d'après notre résultat préliminaire il est facteur de 12i+5 ou de 12i+11 avec i<n. Dans ce cas, on a déjà traité du fait que 4k^2+3 ne peut être un multiple de 12i+5 ou 12i+11 dans notre récurrence
- soit ce nombre est premier: dans ce cas, 4k^2+3 = 0 mod [12n+11] donc
4k^2 = 12n+8 [12n+11]
k^2 = 3n+2 [12n+5]


La question peut donc être ramenée aux 2 questions suivantes (dont je n'ai pas les réponses) :
1) Si 12n+5 est premier; 9n+3 est il un résidu quadratique de 12n+5 ?
2) Si 12n+11 est premier; 3n+2 est il un résidu quadratique de 12n+11 ?
Si la réponse à ces deux questions est "non", alors l'énoncé initial est correct; et si une des 2 réponses au moins est "oui" on est de retour à la case départ.

Pour la question 1, voir l'edit 1
Pour la question 2, voir l'edit 2 smile


Edit:
pour la question 1 finalement, une petite idée: (9n+3) = 3(3n+1). Les propriétés du symbole de Legendre indiquent que 9n+3 est un résidu quadratique si et seulement si 3 et 3n+1 le sont tous deux ou ni l'un ni l'autre.
Or 12n+5 est premier, 3 aussi et donc la loi de réciprocité quadratique indique que 3 est un résidu quadratique de 12n+5 si et seulement si 12n+5 est un résidu quadratique de 3, autrement dit 2 est un résidu quadratique de 3; ce qui est faux.
La question 1) devient donc
1 bis: "Si 12n+5 est premier; 3n+1 est il un résidu quadratique de 12n+5 ?"
La réponse à cette dernière question est le contraire de la réponse 1

Edit bis: pour la question 2, j'ai simplifié ça n'importe comment. Je vais replancher dessus

 #11 - 28-06-2011 12:57:06

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

oremiers modulo 12 : étape 2

Intéressant je vais m'y pencher dès ce soir.
Merci.smile


Un mathématicien complet est topologiquement fermé!

 #12 - 29-06-2011 12:19:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

Premiers modulo 1 : étape 2

Voici donc la démo tant attendue de l'étape 2
Supposons que 4k^2+3 = p.q avec p=5[12] et q=11[12]

Dans le topic du problème général, je montre déjà que p n'est pas premier.
Je le ramène ici vite fait:
- on pose p = 12a+5 qu'on suppose premier
- on montre que 9a+3 doit être un résidu quadratique de 12a+5
- grâce au lemme de Gauss, on montre que 12a+4 est un résidu quadratique de 12a+5
- grâce aux opérateurs sur le symbole de Legendre et au fait que 2*2 = 4, on montre que 3a+1 est un résidu quadratique de 12a+5
- grâce à la loi de réciprocité quadratique, on montre que 3 n'est pas un résidu quadratique
- grâce aux opérateurs sur le symbole de Legendre, on montre que 3(3a+1)=9a+3 n'est pas un résidu quadratique de 12a+5 et donc que p n'est pas premier

On va maintenant montrer que q n'est pas premier d'une manière similaire.
- on pose q = 12b+11 qu'on suppose premier.
- on montre que 3b+2 doit être un résidu quadratique de 12b+11
- grâce au lemme de Gauss, on montre que 12b+8=-3 n'est pas un résidu quadratique de 12b+11 (il suffit de compter, il y a 6b+5 nombres dont 4b+3 supérieurs strictement à 6b+5; et 4b+3 est impair)
- on remarque que 2*2=4 donc 4 est un résidu quadratique de 12b+11
- grâce aux opérateurs sur le symbole de Legendre et au fait que 12b+8 = 4(3b+2), on montre que 3b+2 n'est pas un résidu quadratique de 12b+11

Du coup, on sait maintenant que p ET q ne sont pas premiers; donc 4k^2+3 n'admet aucun facteur premier autre que ceux congrus à 1 et à 7 modulo 12.

Cependant, 1^x = 1[12] et 7^x=1[12] si x et pair et 7^x=7[12] si x est impair; donc en multipliant des facteurs premiers de 4k^2+3 on n'obtiendra que des nombres congrus à 1 ou à 7 modulo 12; en aucun cas des nombres congrus à 5 ou 11.

CQFD

 #13 - 29-06-2011 17:27:39

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premiers modulo 12 : étap 2

Supposons 4k²+3=(3a+2)(3b+2).
Alors a+b=1[2] donc 4k²+3=(6u+2)(6v+5), d'où 4k²+3=4[6].
Or on avait déjà vu que 4k²+3=7[12] et 6 ne divise pas 7-4, absurde.


smile


Un mathématicien complet est topologiquement fermé!

 #14 - 29-06-2011 17:48:55

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

Premiers modulo 12 étape 2

J'adore le "alors a+b = 1[2]", balancé comme si c'était trivial, alors que c'est trivialement faux wink
4k^2+3 est impair => 3a+2 est impair et 3b+2 aussi => a est impair et b aussi
=> a=b=1[2]

Du coup, la suite devient 4k^2+3=(6u+5)(6v+5) = 1[6]; et 6 divise bien 7-1

 #15 - 29-06-2011 17:59:00

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

premierd modulo 12 : étape 2

Oups, j'espère qu'il existe une preuve simple quand même!


Un mathématicien complet est topologiquement fermé!

 #16 - 30-06-2011 14:02:49

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premiers modulo 12 : étappe 2

J'ai une idée.

[latex]4k^2+3=(2k+i\sqrt{3})(2k-i\sqrt{3})[/latex] .
Maintenant soit [latex]p=2[3][/latex] divisant [latex]4k^2+3[/latex] un premier.
Montrons que p ne peut s'écrire comme produit [latex]p=(a+i\sqrt{3}b)(c+i\sqrt{3}d)[/latex], en effet [latex] p^2=(a^2+3b^2)(c^2+3d^2)[/latex] d'où [latex]p=a^2+3b^2[/latex], or [latex]a^2=0 [/latex] ou [latex] 1 [/latex] modulo  [latex] 3[/latex].

Maintenant [latex]p [/latex]divise donc [latex]2k+i\sqrt{3}[/latex] ou [latex]2k-i\sqrt{3}[/latex] car les termes qui forment [latex] p[/latex] ne peuvent provenir séparement de ces deux éléments.

Mais si par exemple [latex]p[/latex] divise [latex]2k+i\sqrt{3}[/latex] alors [latex]p(a+i\sqrt{3}b)=2k+i\sqrt{3}[/latex], impossible.

Il y a sans doute des erreurs...

smile


Un mathématicien complet est topologiquement fermé!

 #17 - 30-06-2011 14:24:06

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

premuers modulo 12 : étape 2

Dans ton [latex]p^2[/latex], je pense qu'il manque des produits croisés...

[latex]\left( a + i \sqrt {3} b \right)^2 = a^2 - 3 b^2 + 2 \sqrt{3} b i[/latex], non ?


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #18 - 30-06-2011 16:21:13

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

oremiers modulo 12 : étape 2

J'ai pris le module complexe au carré.smile


Un mathématicien complet est topologiquement fermé!

 #19 - 30-06-2011 19:08:22

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

premiers modulp 12 : étape 2

Il est bien dommage qu'on ignore ce que j'ai écrit tantôt, car il me semble que la preuve que j'avance est bien plus courte.

 #20 - 30-06-2011 19:22:53

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premierrs modulo 12 : étape 2

Moi ça m'intéressent Nodgim, si tu as plus court n'hésites pas!


Un mathématicien complet est topologiquement fermé!

 #21 - 30-06-2011 20:06:55

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Preemiers modulo 12 : étape 2

En fait ma preuve est correcte, je pense, mais on doit admettre par exemple que [latex]\mathbb{Z}[i\sqrt{3}][/latex] est factoriel pour utiliser le lemme d'Euclide.


Un mathématicien complet est topologiquement fermé!

 #22 - 30-06-2011 20:21:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

premiers modulp 12 : étape 2

Yanyan a écrit:

Moi ça m'intéressent Nodgim, si tu as plus court n'hésites pas!

Ben y a qu'à lire ce que j'ai écrit tantôt....

 #23 - 30-06-2011 20:30:38

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Premiers moudlo 12 : étape 2

Tu parles de ton crible?
Si oui la preuve n'a pas l'air si simple.


Un mathématicien complet est topologiquement fermé!

 #24 - 30-06-2011 22:54:04

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

premiers lodulo 12 : étape 2

Je cite ce que tu as écrit tantôt
Comme 4n²+3 est un 12k+7 (si n non triple), ça ne peut être obtenu que par un produit de premiers dans lequel il y a au moins un 7 modulo 12: en effet, modulo 12, on peut avoir comme premier autre que 7: un 1 un 5 ou un 11, mais leur produit ne donne aucun 7. il y aura donc nécessairement un premier 7 modulo 12 dans un 4n²+3 si n non triple.

Pour moi 5*11=7 [12] donc ton raisonnement ne tient plus (désolé)

Sinon pour la preuve de yanyan ok en admettant ce qu'il fait en effet (je pense qu'en le démontrant effectivement ta demo risque d'être encore plus complexe que la mienne ^^)

 #25 - 01-07-2011 07:23:17

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

premiers modulo 12 : étapr 2

Je sais pas si c'est plus compliqué que par exemple le réciprocité quadratique (c'est complexe d'acccord, la présence de i le confirme).
Moi l'idée me plait et c'est la première fois que j'utilise les complexes en arithmétique classique.
smile


Un mathématicien complet est topologiquement fermé!

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete