Une question de primalité

FrançoisD
FrançoisD
dans Arithmétique
Bonjour,

le nombre $4^{545}+545^4$ est-il premier?

(j'ai la réponse si vous en doutez chafouins que vous êtes! :-P)

Amicalement,

F.D.

Réponses

  • GreginGre
    GreginGre
    Mapeul me dit que non ;-)
  • Jer anonyme
    Jer anonyme
    Ce nombre est divisible par $73$ car $4^{545}=2\pmod{73}$ et $545^4=71\pmod{73}$.
  • discret
    discret
    Identité de Sophie Germain.
  • nicolas.patrois
    nicolas.patrois 
    #!/usr/bin/python
# -*- coding: utf-8 -*-

from random import randint

def estpremier(n):
  d=n-1
  s=0
  while d%2==0:
    s+=1
    d/=2
  for _ in xrange(k):
    a=randint(2,n-2)
    x=pow(a,d,n)
    if x==1 or x==n-1:
      continue
    c=False
    for _ in xrange(s-1):
      x=pow(x,2,n)
      if x==1:
        return False
      if x==n-1:
        c=True
        break
    if c:
      continue
    return False
  return True

k=20
print(estpremier(4**545+545**4))
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Fin de partie
    Fin de partie
    un petit coup de isprime() dans Pari et c'est fini ! :-)

    Je n'ai pas compris la référence à l'identité de Sophie Germain qui est, sauf erreur:

    $x^4+4y^4=(\big (x+y)^2+y^2\big)\big ((x-y)^2+y^2\big)$

    PS:
    Le nombre donné dans le premier message est aussi divisible par $9677$
  • GreginGre
    GreginGre
    Ben, $4^{545}+545^4=545^4+4\cdot (4^{136})^4.$
  • Fin de partie
    Fin de partie
    Merci


    $679369$ divise aussi ce nombre B-)-
  • Jer anonyme
    Jer anonyme
    Ah ! alors,
    \[4^{545}+545^4=545^4+4\times\bigl(4^{136}\bigr)^4=\bigl((545+4^{136})^2+4^2\bigr)\bigl((545-4^{136})^2+4^2\bigr)\]
    et les facteurs valent...
    11517219314030582739994978579676113558706424622852906580737934265886304206
    519009775168733424412166571730937545923222960352700101270845940202114383005
    8550044993554497
    et
    11517219314030582739994978579676113558706424622852906580737934265886304206
    519008120864754888439754616876657516520404022678126220933284874205609214720
    1746344389937217.
    Mais j'ai un plus petit facteur et en plus il est premier...

    Edit: multi-grillé et avec une faute de frappe. Mais j'ai toujours le plus petit facteur premier...
  • Fin de partie
    Fin de partie
    L'un des facteurs obtenu par l'identité de Sophie Germain est divisible par $679369$
    tandis que l'autre est divisible par $73$ et $9677$.
    Mais en divisant ces deux grands nombres par leur facteurs connus, le résultat n'est pas un nombre premier dans les deux cas. :-D
    La factorisation va être coton.

    (si j'ai bien vu, il n'y a pas de diviseurs, autres que ceux déjà trouvés inférieurs à $200 000 000$)

    PS:
    J'ai factorisé l'un des deux gros facteurs :)
  • Fin de partie
    Fin de partie
    Trois autres facteurs (tous premiers) moins triviaux:

    $9213479982293$

    $322326610971024773$

    $54898967567998143011198247530905627154282483189341522981181045317168022956956\\185672843704293807109173205486465482069277905641813$
  • Fin de partie
    Fin de partie
    Pas certain que le facteur qui reste à factoriser puisse l'être avec un esclave numérique courant. :-D
  • Cidrolin
    Cidrolin
    Un des exercices du livre de Titu Andreescu, Mathematical Olympiad Challenges est :37721
  • discret
    discret
    C'est aussi un des exercices du livre de O. Bordellès, Thèmes d'Arithmétique, Ellipses, page 84, traité, justement, avec l'identité de Sophie Germain rappelée ci-dessus par Fin de Partie (curieux, d'ailleurs, que ce dernier ne se souvienne plus de ce truc...).
  • Fin de partie
    Fin de partie
    Discret:

    Il n'y a rien de curieux, $545$ n'étant pas divisible par $4$ j'en ai conclu très hâtivement qu'on ne pouvait pas appliquer cette identité :-D

    PS:
    Cela fait plus d'une heure que j'ai lancé mon esclave numérique pour factoriser le gros facteur qui reste à factoriser et toujours rien. (j'ai lancé mon programme tout pourri évoqué dans un autre fil sans résultat non plus)
  • FrançoisD
    FrançoisD
    Salut à tous,

    bravo pour ceux qui ont pensé à Sophie Germain
    $a^4+4b^4=(a^2+2b^2+2ab)(a^2+2b^2-2ab)$

    et GreginGre l'a superbement bien appliqué

    référence: Engels "Mathematical problems", il s'agit ici d'une olympiade polonaise je crois

    Amicalement,

    F.D.
  • Cidrolin
    Cidrolin
    C'est aussi le problème 493 d'Andrzej Makowski dans le Mathematics Magazine Volume. 35, No. 4 de Septembre Octobre 1962.
  • discret
    discret
    Ce fil permet de rendre hommage à la talentueuse Sophie Germain, dont on pourrait parler plus, et qui gagna sa célébrité, rappelons-le, en démontrant habilement le premier cas du Grand Théorème de Fermat pour tout exposant premier de Sophie Germain (i.e. $p$ et $2p+1$ premiers).

    L'identité ci-dessus sert à démontrer la non-primalité de pas mal de grands entiers. Il me semble qu'il y a quelques années, un intervenant (peut-être Géo ou encore FrançoisD) avait également demandé si $N = 3^{4^5} + 4^{5^6}$ était premier et, là encore, l'identité de Sophie Germain permet de conclure aisément.
  • Cidrolin
    Cidrolin
    Notons qu'une solution au problème de Makowski envisage les valeurs de $n$ modulo $10$.

    Il y a une faute $4^{10}=1048576=6$ mod $10$ et une autre dans $5+4$.37737
  • Fin de partie
    Fin de partie
    Lire la biographie de Sophie Germain sur Wikipedia.

    Elle aurait résidé Rue de Savoie dans le 6ème arrondissement de Paris ( http://fr.wikipedia.org/wiki/Rue_de_Savoie_(Paris) ) où elle y est décédée en 1831 (11 mois avant Galois)
    Elle est la première femme a pouvoir assister aux travaux de l'Institut sans être l'épouse d'un de ses membres.
    C'est dans ce cadre qu'elle a relaté la grossièreté de Galois, si je me souviens bien . B-)-

    PS:
    Factoriser complètement le dernier facteur est désespéré je le crains. :-D
  • discret
    discret
    Ce n'est pas pour chipoter, mais Wikipédia n'est pas mon premier réflexe pour obtenir des références mathématiques.

    Plus haut, j'ai utilisé : P. Ribenboim, Nombres Premiers : Mystères et Records, PUF, 1994.
  • Fin de partie
    Fin de partie
    Wikipedia fait une synthèse de ce qu'on trouve dans des livres courants.
    Il semble qu'aucun livre bibliographique n'ait été consacré exclusivement à Sophie Germain (j'ai cherché en vain jusqu'à maintenant).

    Dans une autre biographie ( http://www.pbs.org/wgbh/nova/physics/sophie-germain.html ) on apprend qu'elle ne s'est jamais mariée. Ce qui j'imagine est assez rare à son époque.
    Elle n'est pas issue de l'aristocratie. Elle vivait de ses rentes. B-)-

    PS:
    La version anglaise de Wikipedia de sa biographie donne plus de détails d'ordre bibliographique.
    On y apprend, par exemple, qu'elle y est enterrée au "Père Lachaise"
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 26

BibixCidrolinFoysGaBuZoMeuMatricule_63SethMorleyJuniorgai requinnatounou +18 Invités