Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Crible carré Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=scarta]Soit s(n) le nombre de carrés dans Zn - i.e. le nombre de y dans 0..n-1 présentant une solution à x²=y, modulo n Soit q(n) le nombre de résidus quadratiques dans Zn - les y ci-dessus qui sont premiers avec n. Montrons que s et q sont multiplicatives - i.e. si m et n sont premiers entre eux, s(m.n) = s(m).s(n) et idem q(m.n) = q(m).q(n) Soient m et n premiers entre eux : Z(m.n) est identique à Zm x Zn, à un isomorphisme près z -> la paire (z mod m, z mod n) - Soient un carré dans Z(m.n) : x et y tels que x² = y mod m.n, on a (x mod m)² = (y mod m) mod m.n, et idem mod n. - Soient un carré dans Zm et un autre dans Zn : (x1x2)² = (y1y2) mod m.n Tout carré dans Z(m.n) correspond donc à une paire de carrés (un dans Zm et un dans Zn) et vice versa : donc s(mn) = s(m).s(n). De là, on montre pareil pour q puisque y premier avec m.n implique y premier avec m et y premier avec n. Une fois ce résultat démontré, considérant la décomposition en nombres premiers n=produit(p_i^alpha_i), s(n)=produit(s(p_i^alpha_i)) et idem pour q Reste plus qu'à déterminer s et q pour des puissances de nombres premiers. Soit p premier. Les carrés de Z(p^n) se décomposent en deux parties : - les résidus quadratiques - et les autres qui ne sont pas premiers avec p^n ==> donc multiples de p Un carré non résidu est donc multiple de p (et même de p² puisque carré). On obtient donc la formule suivante s(p^n) = q(p^n) + s(p^(n-2)) En effet, puisque chaque carré non résidu est un multiple de p², il correspond à un carré modulo p^(n-2) multiplié par p² ensuite Exemple avec les puissances de 3 3^2 - 1, 4, 7 résidus - 0 carré 3^4 - 1, 4, 7 , 10 , 13 , 16 , 19 , 22 , 25 , 28 , 31 , 34 , 37 , 40 , 43 , 46 , 49 , 52 , 55 , 58 , 61 , 64 , 67 , 70 , 73 , 76 , 79 résidus - 0, 9, 36, 63 autres carrés Et (0, 9, 36, 63) sont bien 9* (0, 1, 4 7) trouvés pour 3^2 A partir de là c'est plus facile. On peut trouver q pour p impair à partir de l'indicatrice phi (c'est phi/2) Phi est elle même est vachement simplifiée par le fait qu'on considère p^n, et phi(p^n) = p^(n-1)(p - 1) ou encore p^n - p^(n-1) Accessoirement, s(p^0) = s(1) = 1 et s(p) = q(p) + 1 (puisque tous les carrés sont des résidus sauf 0) En faisant marcher la formule de récurrence, on a s(p^2k) = q(p^2k) + q(p^2k-2) + q(p^2k-4) + ... + q(p²) + s(p^0) = somme((-p)^j, j=1..2k)/2 + 1 = (p^(2k+1)-p)/2(1+p) + 1 s(p^(2k+1)) = q(p^2k+1) + q(p^2k-1) + q(p^2k-3) + ... + q(p^3) + q(p) + 1 = -somme((-p)^j, j=0..2k+1)/2 + 1 = (p^(2k+2)-1)/2(p+1) + 1 En rentrant le 1 sur le même dénominateur, on a - s(p^n) = (p * (p^n + 1) + 2) / (2p+2) pour n pair - s(p^n) = (p * (p^n + 2) + 1) / (2p+2) pour n impair C'est joli non ? Par exemple, pour 45, on a s(9)s(5) = 43 = 12, et il y en a effectivement 12 : 0 , 1 , 4 , 9 , 10, 16 , 19, 25 , 31, 34, 36 et 40 Pour p=2, je me rappelle plus, mais y'avait une astuce. Ca me reviendra Ca n'aidera pas à calculer ta limite :) Mais je trouvais la formule jolie[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Dans une course, vous doublez le 20ème, en quelle position êtes-vous ? Retour Résumé de la discussion Sydre 18-07-2020 15:31:40 Salut On note [latex]\sigma[/latex] la fonction qui à [latex]n\in\mathbb{N}[/latex] associe le nombre de restes [latex]r\in\mathbb{N}<n[/latex] tels que [latex]nq+r[/latex] puisse être carré avec [latex]q\in\mathbb{N}[/latex] Par exemple [latex]\sigma(3)=2[/latex] car un carré peut être de la forme [latex]3q+0[/latex] ou [latex]3q+1[/latex] mais pas [latex]3q+2[/latex] Expliciter [TeX]\lim_{n\to +\infty}\frac{\sigma(n)}{n}[/TeX] Spoiler : [Afficher le message] 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