Propriétés de la fonction phi d'Euler
Répondre à la discussion
Affichage des résultats 1 à 14 sur 14

Propriétés de la fonction phi d'Euler



  1. #1
    anthony_unac

    Propriétés de la fonction phi d'Euler


    ------

    Bonjour,

    Existe t il une propriété de la fonction phi d'Euler permettant de résoudre simplement l'équation en suivante sachant que est premier :
    **********************


    et de façon générale :
    ******************
    (avec k une constante entière)

    Cordialement
    Anthony

    -----

  2. #2
    Thorin

    Re : Propriétés de la fonction phi d'Euler

    Salut,
    déjà, si m est premier, phi(m)=m-1
    École d'ingénieurs + M1 Physique Fondamentale

  3. #3
    Thorin

    Re : Propriétés de la fonction phi d'Euler

    Ensuite, et bien on connait la formule qui relie phi(m-1) à la décomposition en facteurs premiers de m-1, on peut alors raisonner dessus...
    École d'ingénieurs + M1 Physique Fondamentale

  4. #4
    anthony_unac

    Re : Propriétés de la fonction phi d'Euler

    Citation Envoyé par Thorin Voir le message
    Salut,
    déjà, si m est premier, phi(m)=m-1
    Exact je viens de lire ça sur cet article de wikipédia.

  5. A voir en vidéo sur Futura
  6. #5
    anthony_unac

    Re : Propriétés de la fonction phi d'Euler

    Citation Envoyé par Thorin Voir le message
    Ensuite, et bien on connait la formule qui relie phi(m-1) à la décomposition en facteurs premiers de m-1, on peut alors raisonner dessus...
    La par contre je ne suis pas vraiment.
    Prenons l'exemple m=13
    ********************

    (valeur lue sur une table)
    C'est très simple !

    Mais alors l'exemple suivant l'est beaucoup moins :
    ****************************** *********

    On peut essayer de résoudre à tâtons en se disant que est premier donc :
    est pair mais ne se termine pas par un 4
    Ensuite repérer sur une table toutes les valeurs pour lesquelles l'indicatrice d'Euler vaut 12 mais la ça fait un paquet de candidats :
    phi(42)
    phi(26) mais comme 27 n'est pas premier on l'élimine
    phi(36)
    phi(28)

    Ou alors tous ces candidats sont solution de l'équation et on aboutit à l'ensemble des solutions

  7. #6
    invite4ef352d8

    Re : Propriétés de la fonction phi d'Euler

    Salut !

    les nombres entier tel que Phi(n) = k pour un k fixé sont toujours en nombre fini il me semble. regardons le cas de k=4.

    soit n tel que Phi(n)=4

    si n=p1^a1 ... Pk^ak

    alors Phi(n)= (p1-1)p1^(a1-1) ... (pk - 1)pk^(ak-1)

    si l'un des Pi est plus grand (strictement) que 5, alors pi-1 >4 impossible.
    de même si pi=5 ou 3, alors ai=1 sinon (pi-1)pi^(ai-1)>4

    et de même si pi=2, alors ai<4

    ca te laisse un nombre fini d'entier à tester.

    les solution de ton equation sont les n+1 tel que phi(n)=4 et n+1 est premier.

  8. #7
    Thorin

    Re : Propriétés de la fonction phi d'Euler

    les nombres entier tel que Phi(n) = k pour un k fixé sont toujours en nombre fini il me semble
    Effectivement, car
    d'où
    École d'ingénieurs + M1 Physique Fondamentale

  9. #8
    anthony_unac

    Re : Propriétés de la fonction phi d'Euler

    Citation Envoyé par Ksilver Voir le message
    Salut !

    les nombres entier tel que Phi(n) = k pour un k fixé sont toujours en nombre fini il me semble. regardons le cas de k=4.

    soit n tel que Phi(n)=4

    si n=p1^a1 ... Pk^ak

    alors Phi(n)= (p1-1)p1^(a1-1) ... (pk - 1)pk^(ak-1)

    si l'un des Pi est plus grand (strictement) que 5, alors pi-1 >4 impossible.
    de même si pi=5 ou 3, alors ai=1 sinon (pi-1)pi^(ai-1)>4

    et de même si pi=2, alors ai<4

    ca te laisse un nombre fini d'entier à tester.

    les solution de ton equation sont les n+1 tel que phi(n)=4 et n+1 est premier.
    Merci pour votre réponse mais je dois avouer que je reste sur le c**
    Il n'y aurait donc aucune façon de résoudre proprement ce type d'équation ?
    Mais alors si on reste dans l'expérimentation pour résoudre ce type d'équation alors qu'est ce que ça va être quand on va s'attaquer à ça :
    **********************
    Montrer que admet au moins un diviseur premier

  10. #9
    Thorin

    Re : Propriétés de la fonction phi d'Euler

    Ensuite, on peut utiliser
    (avec )

    Prenons par exemple l'équation (avec m premier)

    on a donc, en remplaçant n par m-1 dans la formule du début de ce post :



    pour que cette égalité soit vérifiée, il faut la multiplicité de 7 dans le membre de droite soit 1.
    pour ça :
    -soit 7 divise m-1 avec une multiplicité supérieure à 2, mais c'est exclut car dans ce cas, 6 diviserait 28.
    -soit le 7 vient des "" donc ou , mais comme 15 n'est pas premier, il ne reste que . Et comme 29 ne divise pas 28, on en déduit que la multiplicité de 29 dans m-1 est de 1.
    finalement, m-1=29, ce qu'on exclut.

    finalement, il n'existe pas de solution à cette équation.
    École d'ingénieurs + M1 Physique Fondamentale

  11. #10
    invite4ef352d8

    Re : Propriétés de la fonction phi d'Euler

    "Montrer que admet au moins un diviseur premier " >>> bonne nouvel : tous les entier naturel >1 admettent un diviseur premier !


    et puis au fond tu t'attendais à quoi ? une formule close avec des racines carré pour exprimer les solutions de l'equation ?

    je te rapelle quand même que rien que connaitre la valeur de phi(n) pour tous n, c'est déjà connaitre tous les nombres premier, et c'est quasiement savoir factoriser tous les entiers. (ce n'est pas prouvé dans le cas général, mais il est communement accepter que savoir calculer phi(n) pour un n donné est un problème aussi difficile que savoir factoriser n en nombre premier. et l'algorithme le plus efficace pour calculer phi(n), c'est de factoriser n en nombre premier et d'utiliser la formule que j'ai donné...

  12. #11
    anthony_unac

    Re : Propriétés de la fonction phi d'Euler

    Citation Envoyé par Ksilver Voir le message
    "Montrer que admet au moins un diviseur premier " >>> bonne nouvel : tous les entier naturel >1 admettent un diviseur premier !
    On va (dans ce cas) changer l'énoncé :
    *****************************
    Déterminer m tel que
    Ce que vous aviez très bien compris au préalable


    et puis au fond tu t'attendais à quoi ?
    Le *vous* n'est pas mal non plus quand vous ne connaissez pas (suffisamment) les gens que vous abordez.

    Je
    ...un premier je ?

    te
    Suivi du tutoiement


    rapelle quand même que rien que connaitre la valeur de phi(n) pour tous n, c'est déjà connaitre tous les nombres premier, et c'est quasiement savoir factoriser tous les entiers. (ce n'est pas prouvé dans le cas général, mais il est communement accepter que savoir calculer phi(n) pour un n donné est un problème aussi difficile que savoir factoriser n en nombre premier. et l'algorithme le plus efficace pour calculer phi(n), c'est de factoriser n en nombre premier et d'utiliser la formule que j'ai donné...
    Ok Ksilver nous sommes donc face à un problème très difficile.
    Merci de le faire savoir aussi gentiment.

    Bien cordialement
    Anthony

  13. #12
    hhh86

    Re : Propriétés de la fonction phi d'Euler

    Anthony_unac, ce que Ksilver voulait vous signalez dans un premier temps et il n'a pas tord est que si 6?+5? (en adoptant votre notation) est premier, alors dans ce cas m=6?+5?
    La démontrabilité est la raison. L'autorité n'est qu'affirmation

  14. #13
    anthony_unac

    Re : Propriétés de la fonction phi d'Euler

    Citation Envoyé par hhh86 Voir le message
    Anthony_unac, ce que Ksilver voulait vous signalez dans un premier temps et il n'a pas tord est que si 6?+5? (en adoptant votre notation) est premier, alors dans ce cas m=6?+5?
    Oui oui j'avais bien compris et je ne doute pas non plus qu'il est parfaitement compris qu'il s'agissait d'un diviseur premier autre que l'éventuel 5?+6? lui même mais bon qu'importe.

  15. #14
    invite4ef352d8

    Re : Propriétés de la fonction phi d'Euler

    Je ne voulez en aucun cas être offensant. si vous ai tutoier, c'est parceque c'est il me semble la tradition sur ce forum. Et ma première remarque était juste une façon ironique de signaler que je ne comprenais pas ce que vous souhaitiez faire : montrer que 5?+6? n'est pas premier, ou en trouver un diviseur premier strict ?. qui sont deux problème extrement distinct (le deuxième est infiniment plus difficile que le premier).


    la suite de mon message était juste là pour essayer de vous convaincre que d'une part essayer d'étudier la primalité de grand nombre en calculant Phi(n) n'est pas une bonne idée du tous, et d'autre part d'essayer de vous faire comprendre pourquoi il n'y à effectivement rien de clairement plus simple que ce que j'ai proposé plus haut. (biensur on peut améliorer legement de facon à "automatiser" cette recherche de solution pour un 'k' quelconque, mais fondamentalement, ca va rester le même genre de raisonement...)

Discussions similaires

  1. Fonction beta d'Euler
    Par invitee51caab2 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 14/05/2008, 23h29
  2. Fonction Gamma d'Euler
    Par invite5e5dd00d dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 07/03/2008, 10h44
  3. Fonction indicatrice d'Euler...
    Par invite43bf475e dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/11/2007, 13h43
  4. Algorithme de calcule de la fonction phi d'Euler
    Par invite8c3060a6 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 22/02/2007, 11h38
  5. fonction indicatrice d'Euler
    Par invite0f71df23 dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 29/01/2007, 08h58