Maths et Délires

[Jill-Jênn]

L'entier naturel [tex:beb1ebd662]n[/tex:beb1ebd662] est décomposé en facteurs premiers sous la forme :
[tex:beb1ebd662]n = p_1^{\alpha_1} \ldots p_s^{\alpha_s}[/tex:beb1ebd662]
Déterminer le nombre de classes modulo [tex:beb1ebd662]n[/tex:beb1ebd662] qui vérifient la congruence [tex:beb1ebd662]x^2 \equiv x [n][/tex:beb1ebd662].

Pour les PTBD, on va remplacer "nombre de classes modulo [tex:beb1ebd662]n[/tex:beb1ebd662]" par "nombre de [tex:beb1ebd662]x[/tex:beb1ebd662] non congrus deux à deux modulo [tex:beb1ebd662]n[/tex:beb1ebd662]".

Au fait, vous saviez que \frac a b ça donnait pareil que \frac{a}{b} ? Je viens de découvrir ça par accident
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Tom]

Tu as la mémoire courte : http://boumbo.toonywood.org/mathetdelire/forum/viewtopic.php?p=39537&highlight=latex#39537

[Jill-Jênn]

Ça va, c'était le lendemain de mon anniversaire, j'avais encore la gueule de bois

Hé, je plaisante les gens, revenez
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Abou]

Qui sont les PTBD?

[Thibaut]

Passe Ton Bac D'abord
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal

[Jill-Jênn]

Abou, il ne t'intéresse pas, cet exercice ? Oui je sais qu'on a autre chose à faire. Mais passer un peu de temps dessus ne fait pas de mal. Et je posterai ce que je crois être une solution bientôt ^^
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Abou]

Ben c'est que ça m'rappelle 'achement ce que j'ai fait y'a pas si longtemps (dans la semaine), à savoir l'épreuve de Math II des mines 2002.

Bon, j'vais voir ça en mangeant

Édit : ha non en fait ça n'y ressemble pas du tout.

[Djina]

A Jill-Jênn: Je te suis très reconnaissante pour tes explications de hier, mais je ne vois absolument pas en quoi ça peut m'aider à résoudre le problème...

[Jill-Jênn]

Je pense qu'il est mieux que je donne ma solution, que je t'expliquerai si besoin est. C'est pas un bon premier exercice d'arithmétique (au fait, c'est le tout premier de la planche de Classiques n°2, il est dans la section "Proches du cours" alors que pas du tout xD).

Je la posterai un peu après 23h

Edit (00:17) : Soit [tex:872250dc4f]x[/tex:872250dc4f] une telle classe.
Nécessairement, [tex:872250dc4f]\exists k~|~x^2 = x + k n[/tex:872250dc4f]
[tex:872250dc4f]x(x - 1) = k p_1^{\alpha_1} \ldots p_s^{\alpha_s}[/tex:872250dc4f]
Or [tex:872250dc4f]x[/tex:872250dc4f] et [tex:872250dc4f]x - 1[/tex:872250dc4f] sont premiers entre eux, donc d'après Gauss itéré, [tex:872250dc4f]\forall i,~p_i^{\alpha_i}|x[/tex:872250dc4f] ou [tex:872250dc4f]p_i^{\alpha_i}|x - 1[/tex:872250dc4f].
Donc [tex:872250dc4f]x[/tex:872250dc4f] est de la forme [tex:872250dc4f]k_1 a[/tex:872250dc4f] ([tex:872250dc4f]a[/tex:872250dc4f] est le produit des [tex:872250dc4f]p_i^{\alpha_i}[/tex:872250dc4f] qui divisent [tex:872250dc4f]x[/tex:872250dc4f]) et [tex:872250dc4f]x - 1[/tex:872250dc4f] de la forme [tex:872250dc4f]k_2 b[/tex:872250dc4f] où [tex:872250dc4f]a[/tex:872250dc4f] et [tex:872250dc4f]b[/tex:872250dc4f] sont premiers entre eux et [tex:872250dc4f]a b = n[/tex:872250dc4f].

Réciproquement, pour tout produit [tex:872250dc4f]a[/tex:872250dc4f] de [tex:872250dc4f]p_i^{\alpha_i}[/tex:872250dc4f], si on note [tex:872250dc4f]b = n / a[/tex:872250dc4f], on a bien [tex:872250dc4f]a[/tex:872250dc4f] et [tex:872250dc4f]b[/tex:872250dc4f] premiers entre eux, donc d'après Bézout il existe [tex:872250dc4f]k_1[/tex:872250dc4f], [tex:872250dc4f]k_2[/tex:872250dc4f] tels que :
[tex:872250dc4f]k_1 a - k_2 b = 1[/tex:872250dc4f]
Donc en prenant [tex:872250dc4f]x = k_1 a[/tex:872250dc4f], on a [tex:872250dc4f]x - 1 = k_2 b[/tex:872250dc4f] et [tex:872250dc4f]x(x - 1) = k_1 k_2 n[/tex:872250dc4f], d'où [tex:872250dc4f]x^2 \equiv x [n][/tex:872250dc4f].

Montrons que les [tex:872250dc4f]x[/tex:872250dc4f] obtenus ne sont pas congrus 2 à 2 modulo [tex:872250dc4f]n[/tex:872250dc4f].
Pour ce faire, supposons par l'absurde qu'[tex:872250dc4f]\exists x, x'~|~x \equiv x' [n]~(1)[/tex:872250dc4f] et [tex:872250dc4f]\exists p_i~|~p_i | x[/tex:872250dc4f] et [tex:872250dc4f]p_i \not | x'[/tex:872250dc4f].
[tex:872250dc4f](1) \Leftrightarrow p_i | x - x'[/tex:872250dc4f], donc comme [tex:872250dc4f]p_i | x[/tex:872250dc4f], on a [tex:872250dc4f]p_i | x'[/tex:872250dc4f], contradiction.

Finalement, il y a autant de [tex:872250dc4f]x[/tex:872250dc4f] qui conviennent que de parties de [tex:872250dc4f]\{1, \ldots, s\}[/tex:872250dc4f] (chaque partie représente les indices des nombres premiers choisis dans la décomposition en facteurs premiers de [tex:872250dc4f]a[/tex:872250dc4f]), c'est-à-dire [tex:872250dc4f]\fbox{$2^s$}[/tex:872250dc4f].
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Jill-Jênn]

Coucou, c'est juste pour dire que j'ai posté la solution xD Mais comme j'ai édité, vous n'avez peut-être pas vu ^^
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Abou]

Ha oui j'avais pas vu.

Y'a pas à dire, l'arithmétique c'est vraiment pas mon truc. (J'étais partis archi loin, sans rien de convainquant).

[Jill-Jênn]

convaincant*
Il n'était pas convaincant, mais de toute façon, en le convainquant, il n'arriverait pas à obtenir ce qu'il désirait ^^
Il y a l'adjectif et le participe ^^

Est-ce que tu as compris la démo ?
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Tom]

Jill-Jênn, tu devrais pas être en train de dormir à cette heure ci ?? N'oublie pas que c'est rdv à 7h30 mercredi pour les Mines :p
_________________
JJ never dies

[Jill-Jênn]

Dormir à 9h12 ? Nonon, j'étais réveillé ()
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Abou]

Nan j'ai pas compris, déjà dès le début je suis largué :

[Jill-Jênn]

Disons que c'était un peu long à taper

Ah le reste t'as suivi ? Cool !
T'es d'accord que créer un [tex:8d3341fb55]x[/tex:8d3341fb55], ça revient à prendre une partie de [tex:8d3341fb55]\{1, \ldots, s\}[/tex:8d3341fb55]. Eh bien si on prend deux [tex:8d3341fb55]x[/tex:8d3341fb55] différents, ils sont associés à deux parties différentes. Donc il en existe un qui a en facteur un [tex:8d3341fb55]p_i^{\alpha_i}[/tex:8d3341fb55] (donc [tex:8d3341fb55]p_i[/tex:8d3341fb55]) que l'autre n'a pas.
Si on suppose que ces deux [tex:8d3341fb55]x[/tex:8d3341fb55] sont congrus modulo [tex:8d3341fb55]n[/tex:8d3341fb55], on aboutit à une contradiction.
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya

[Abou]

Ha oui je vois, merci =)

[Cerise]

[Jill-Jênn]

[Overlord]

Cherry, a priori, quand on passe à l'heure d'été, on avance l'horloge...
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.

Il y a 11 catégories de gens sur Terre :
- Ceux qui vont sourire à cette blague parce qu'ils connaissent le binaire
- Ceux qui la connaissent et qui connaissent le binaire
- Ceux qui ne comprennent pas
Mais 10 d'entre eux ont VRAIMENT besoin de lâcher leur ordi...