Nouvelle méthode pour trouver le reste d'une division

octobre
Modifié (6 Jan) dans Shtam
Bonjour à toutes et à tous
J'ai bricolé cette méthode pour calculer le reste d'une division, comme vous pouvez le voir dans les exemples.
Les questions auxquelles je réfléchis sont les suivantes.
Question 1.
Dans quels cas cette méthode est-elle meilleure que d'autres pour trouver le reste d'une division ?
Question 2.
Pourrions-nous trouver un moyen de l'utiliser pour tous les exemples (les meilleurs polynômes à choisir pour faciliter le calcul du reste, pour le diviseur ça serait toujours de degré 1 car je sais calculer directement le reste) ?
Exemple 1. Quel est le reste lorsque $10^{124}-5$ est divisé par $33$ ?
Nous avons $(10^{124}–5)/33=(10^{124}–5)/(3*10+3)$.
Je choisis $x=10$, alors j'ai $P1/P2=(x^{124}–5)/(3x+3)$ avec $P1=(x^{124}–5)$ et $P2=(3x+3)$.
En utilisant la division euclidienne des polynômes pour diviser par un polynôme de degré $1$ $P2$, il suffit d'interpoler à la racine du diviseur, ici $x = -1$ car $P2(-1)=0$.
Nous savons que $P1=qP2+r$ avec $r$ de degré zéro.
Et que $r=P1(-1)=(-1^{124}–5)=-4$ ce qui équivaut à $29$ modulo $33$.
Exemple 2. Quel est le reste lorsque $1009^{12}+1$ est divisé par $2017$ ?
Je choisis $x=1009$, alors j'ai $P1/P2=(x^{12}+1)/2017=(x^{12}+1)/(2x - 1)$ avec $P1=(x^{12}+1)$ et $P2=(2x - 1)$.
En utilisant la division euclidienne des polynômes pour diviser par un polynôme de degré $1$ $P2$, il suffit d'interpoler à la racine du diviseur, ici $x = 1/2$ car $P2(1/2)=0$.
Nous savons que $P1=qP2+r$ avec $r$ de degré zéro.
Et que $r=P1(1/2)=(2^{12}+1)/2^12=4097/4096$.
Donc $4096=4097r$ modulo $2017$ avec $r < 2017$. Avec un tableur Excel, nous trouvons $r=489$.
Exemple 3. Quel est le reste lorsque $4^{29}$ est divisé par $63$ ?
Nous avons $(4^{29})/63 = (4^{29})/(4^3–1)$.
Je choisis $x = 4$, alors j'ai $P1/P2 = (x^{29})/(x^3–1)$ avec $P1 = x^{29}$ et $P2 = (x^3–1)$.
En utilisant la division euclidienne des polynômes :
$R=x^2=4^2=16$, le reste est $16$ modulo $63$.

Réponses

  • zygomathique
    Modifié (6 Jan)
    Salut
    vu que la division euclidienne des polynômes est une extension/généralisation de la division euclidienne des entiers dans l'anneau adéquat et avec les propriétés nécessaires/suffisantes.

    EX1 :  tu décides de choisir la base b = x = 10 et d'écrire $10^{124} - 5 = b^{124} - 5 = P_1(b)$ et $33 = 3b + 3 = P_2(b)$ et tu cherches (le reste de) la division euclidienne de $P_1(b)$ par $P_2(b)$.

    EX2 : attention il y a confusion entre 2007 et 2017.
    Tu choisis la base b = 2007 et tu cherches (le reste de) la division euclidienne de $P_1(b) = b^{12} + 1$ par $ P_2(b) = 2b - 11$

    EX3 : tu choisis la base b = 4 et tu cherches (le restes de) la division euclidienne de $ P_1(b) = b^{29}$ par $P_2(b) = b^3 - 1$
    Mézalor dans ce cas le reste est un polynôme du second degré en $b$.

    Ce ne sont pas les signes, les symboles qui constituent la science ; le seul principe qui y domine, c’est l’esprit de sagacité auquel les objets soumis servent d’auxiliaire.                BHASCARA

  • octobre
    Modifié (7 Jan)
    Oui  erreur c'est bien 2017 je vais corriger.
    Oui le dernier exemple montre que même en choisissant un polynôme de diviseur qui n'est pas de degré 1 ça marche aussi.
    En clair si j'ai des grands nombres je peux bien sûr réduire les grands nombres sous forme $P1=x29=x^2*X^{27}=16X^{27}$ et dans le diviseur je remplace $x^3=X$ pour l'exemple 3 j'ai $ r=P1(1)=16$ car $P2=X-1$ et $P2(1)=0$.
  • octobre
    Modifié (7 Jan)
    En fait je veux utiliser cette méthode pour tester rapidement si un nombre sous forme $2^n -1$ est premier ou pas pour $n$ entier impair.

    Il suffit de poser ($2^n  -1)/(2k-1)$  ou ($2^n  -1)/(2k+1)$ 
     $(2^n  -1)/(2k-1)=(x^n  -1)/(2*k-x/2)$ ou $(2^n  -1)/(2k+1)=(x^n  -1)/(2*k+x/2)$,
     donc  $r=(4k)^n-1$ ou $r=(-4k)^n-1$  en tout cas je cherche à écrire le reste en fonction de $k$ et montrer que pour un $n$ donné le reste ne sera jamais nulle $mod$  $2k-1$ ou $2k+1$ et que $q(x)$ n'a pas de diviseur en commun avec $r$. 
  • L'idée est intéressante, bien que très mal formulée, mathématiquement parlant.
    Cependant, cela ne sera pas plus efficace que de faire la division euclidienne.
    En fait, cela demande même plus d'opérations dans tous les cas !
  • octobre
    Modifié (6 Jan)
    Vous êtes sûr car dans le cas de grands nombres ça réduira les calculs énormément et ça se voit dans l'exemple 3 ?
  • gerard0
    Modifié (6 Jan)
    Le troisième exemple est particulier, mais de ce fait se calcule rapidement par les congruences, ainsi :
    $4^3 \equiv 1 [63]$
    $29 = 9\times 3 +2$ donc $4^{29} \equiv 4^2 =16 [63]$
    Même pas de polynômes à diviser ...
  • octobre
    Modifié (6 Jan)

    Oui, je ne dis pas le contraire, parfois on peut trouver des méthodes bien plus faciles, mais pas facilement programmables pour tout, comme cette méthode qu'on peut adapter pour l'utiliser d'une manière générale.

    Mais vraiment, ici mon but est d'utiliser cette méthode pour tester tous les cas de figure avec un polynôme de degré 1 et avec un paramètre entier k>1  , pour savoir directement si un nombre écrit sous  forme polynomial P1 est premier ou non .


  • Bonjour,
    Cette vision où l'on transforme les entiers en polynômes pour faire des calculs est très intéressante mais absolument pas nouvelle.
    Je t'invite à regarder les méthodes de Transformée de Fourier Rapide qui permettent de multiplier efficacement 2 polynômes, et également de faire rapidement une division euclidienne de polynômes. Pour faire efficacement le produit ou la division euclidienne de 2 entiers, une méthode classique est de passer par des polynômes en 10 (ou dans une autre base), où les calculs sont rapides, pour ensuite revenir à des entiers en évaluant.
  • bisam
    Modifié (7 Jan)
    Mais au lieu de dire "on peut le faire"... pourquoi ne le fais-tu pas ?
    Il existe des langages de programmation qui permettent de faire ça de façon très simples et synthétique (comme Python, voire la surcouche qu'est Sage)... mais c'est complètement inutile car ces langages manipulent sans problème des entiers de plusieurs milliers de chiffres.
    Si tu fais un calcul théorique pour voir si ton idée est réalisable ou non, tu verras que le nombre de calculs à effectuer pour répondre à la question que tu te poses (à savoir $2^n-1$ est-il premier ?) est BEAUCOUP plus grand que les méthodes déjà connues pour effectuer CE test en particulier, notamment le test de Lucas-Lehmer, qui est très rapide, même s'il nécessite de travailler sur de nombre potentiellement très grands.
  • octobre
    Modifié (7 Jan)
    @Heuristique
    Oui je sais que ce n'est pas nouveau comme méthode mais ici je souhaite l'utiliser pour tester un nombre de Mersenne si il est permier ou pas et trouver les valeurs de $n$ exactes.
    @bisam
    Avant de passer a la programmation il faut faire la théorie et réduire au max les calculs.
    Pour l'instant j'arrive à écrire le nombre de Mersenne $2^n-1=(2k+1)*Q1+r1$ ou  $2^n-1=(2k-1)Q2+r2$.

    Si $2^n-1$ est permiers alors $r1 \pmod {2k+1}$ ne s'annule pas ou ils n'ont pas de diviseur en commun et $Q1\pmod {r1}$ ne s'annule pas ou ils n'ont pas de diviseur en commun donc je suis curieux de réduire le calcul pour trouver les valeurs exactes de $n$ où $2^n-1$ est premier.
    Et j'ai aussi si $2^n-1$ est premiers alors $r2\pmod {2k-1} $ ne s'annule pas ou ils n'ont pas de diviseur en commun et $Q2\pmod {r2}$ ne s'annule pas ou ils n'ont pas de diviseur en commun donc je suis curieux de réduire le calcul pour trouver les valeurs de $n$ où $2^n-1$ est premier.
    Donc j'ai deux équations avec deux inconnues $k$ et $n$ que je peux le réduire à une seule inconnue $n$  et me servir pour trouver exactement les valeurs de $n$ où $2^n-1$ est premier ce n'est pas juste pour tester si un nombre $2^n-1$ est premier.

    Donc voilà les équations que je cherche à réduire pour trouver les conditions sur $n$ pour que $2^n-1$ soit premier.
     $r1\%(2k+1)=???$ et $Q1\%(2k+1)=??? $ ou  $r2\%(2k-1)=???$ et $Q2\%(2k-1)=???$.
    [Marin Mersenne (1588-1648) prend toujours une majuscule. AD]
  • bisam
    Modifié (7 Jan)
    Si tu n'es pas capable d'écrire correctement 4 phrases mathématiques expliquant ce que tu veux faire, effectivement, cela va être beaucoup plus difficile.
    Faire des maths, c'est faire des raisonnements, pas des calculs. Si tu ne mets aucun quantificateur dans tes phrases, tu ne peux pas raisonner. Si tu ne te rends pas compte que le cas $2k+1$ et le cas $2k-1$ sont en fait le même cas... alors je crois qu'on va s'arrêter là.
  • octobre
    Modifié (7 Jan)
    Oui je sais que 2k+1 et 2k-1 sont la même chose mais ils donnent chacun un Q1 et Q2 et r1 et r2 différents vous avez deux choix.
    Peux-tu faire des math et m'aider  à réduire ces expressions  $((4k)^n-1)\%(2k-1)=?$   ou   $((-4k)^n-1)\%(2k+1)=?$  
  • octobre
    Modifié (7 Jan)
    Bon je pense que il faut surtout réduire le calcul  $((-4k)^n-1)\%(2k+1)=?$  (1)
    Et pour $Q2$ voici ça forme pour $n$ impair :
    Pour $k=1$ et $k=2$ et $k=3$ et $n=5$ on voit bien qu'il est facile de l'écrire en fonction de $n$ et $k$ donc après il faut chercher à réduire le calcul $Q2(2)\%((-4k)^n-1)=?$  (2)
    Donc on réduisant les deux calculs (1) et (2) on peut exactement trouver les valeurs $n$ exactes où $2^n-1$ est premier ce sont les valeurs ou (1) et (2) ne s'annulent pas quelque soit la valeur de $k$.


  • gerard0
    Modifié (7 Jan)
    "Oui je sais que 2k+1 et 2k-1 sont la même chose mais il donne chacun un Q1 et Q2 et r1 et r2 différent"
    Oui, et 2k+3 donne encore un Q3 différent, et 2k+5 encore un Q4 différent et ...
    Essaie de comprendre ce qui t'est expliqué, c'est ridicule de persister ...
    "Errare humanum est, perseverare diabolicum"
  • octobre
    Modifié (7 Jan)
    Bon mon choix est porté sur 2k+1 pourriez-vous résoudre les questions que j'ai posées, je pense que vous avez bien compris la méthode, c'est pourquoi vous avez critiqué juste le choix de diviseurs, avez-vous d'autres critiques aussi ?
  • Je n'ai pas critiqué les choix que tu as fait dans tes calculs car je t'ai dit plus haut que faire des maths, ce n'est pas faire des calculs.
    Faire des maths, c'est RAISONNER, et ensuite EXPLIQUER.
    Nous n'allons pas faire ce travail à ta place. Si tu veux faire des maths, fais-le. Ne demande pas aux autres de le faire à ta place.
  • gerard0
    Modifié (7 Jan)
    Ma principale critique est que tu proposes des calculs pénible pour une question élémentaire, bien connue. Et que tu ne montres pas l'intérêt de faire ce que tu dis.
    Que peux-tu dire en quelques ligne de $2^{20567}-1$ et de $2^{20593}-1$ ? Sont-ils premiers ?
Connectez-vous ou Inscrivez-vous pour répondre.