Équivalence ?

babsgueye
babsgueye
dans Fondements et Logique
Salut les logiciens; je n'en suis pas un !

Soit $T$ la propriété : ''$\big(\varphi(n)\big)^n + 1\equiv 0\bmod n\ $ et $\ Q$ la propriété : ''$n-1\equiv 0\bmod \varphi(n)$''.
Soit $P$ la propriété : ''$n \,\textrm{est premier}$''.
Il est possible de démontrer que : ''$P\,\iff\,T\wedge Q$''.

Je pense que (conjecture) ''$T\,\iff\,Q$''.
Que peut apporter de plus, un raisonnement purement logique ?
Remarque :''$Q\,\iff \,P$'' est la conjecture de Derrick Lehmer.
Merci.

Réponses

  • Poirot
    Poirot
    Quelle est la question ? Si on sait que $P \Leftrightarrow T \wedge Q$ alors $T \Leftrightarrow Q$ implique que $P \Leftrightarrow Q$.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bonjour

    Je plussoie la conclusion de Poirot.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • Calli
    Calli
    Bonjour,
    Ce serait bien de quantifier en $n$ et de noter plutôt $T(n)$, $Q(n)$ et $P(n)$. Par exemple, sans quantification sur $n$, je ne comprends pas le message de PetitLutinMalicieux. Veux-tu dire $$\forall n,\;(P(n) \Leftrightarrow Q(n)) \vee (T(n)\wedge Q(n) \wedge P(n))$$ ou $$ (\forall n, \;P(n) \Leftrightarrow Q(n)) \vee (\forall n,\; T(n)\wedge Q(n) \wedge P(n))\quad ?

    $$ Edit : PetitLutinMalicieux a modifié son message entre temps.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    @Calli : :-D Tu as répondu plus vite que j'ai effacé. J'ai relu de travers mon papier et écrit des bêtises sur le forum.

    Sur mon papier, il y a :
    $(P \Leftrightarrow (T \wedge Q ) ) \Leftrightarrow ( (P \Rightarrow (T \wedge Q ) )\ et\ ( (T \wedge Q ) \Rightarrow P) )$
    $(P \Leftrightarrow (T \wedge Q ) ) \Leftrightarrow ( (\bar P + TQ )(\overline{TQ} + P) )$
    $(P \Leftrightarrow (T \wedge Q ) ) \Leftrightarrow ( (\bar P +TQ )(\bar T + \bar Q + P) )$
    $(P \Leftrightarrow (T \wedge Q ) ) \Leftrightarrow ( \bar P \bar T + \bar P \bar Q + TQP )$

    Donc effectivement, si T=Q, alors P=Q.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • babsgueye
    babsgueye
    Bonjour.

    Tu réponds bien dans le sens de la question @Poirot. Je savais déjà que ''$T\,\implies\,Q$'' implique ''$T\,\iff\,P$'' de mème que :''$Q\,\implies\,T$'' implique ''$Q\,\iff\,P$''. C'est ce que tu viens de dire.

    Si on sait aussi que :''$Q\wedge\bar P$'' implique ''$\bar T$'', et que ''$T\wedge\bar P$'' implique ''$\bar Q$'', mème question; peut-on dire plus ?

    @Calli, je pense qu'on peut bien mettre $T(n),\,Q(n),\,P(n)$.

    Sinon pour la conjecture :''$T\,\iff\,P$'' je n'ai pas fait de vérifications numériques sérieuses. On peut toujours alors essayer de trouver un contre-exemple.
  • claude quitté
    claude quitté 
    [color=#000000]> // F(n) = Phi(n)^n mod n  ET F(n) in [0..n-1]                                                    
> F := func < n | Modexp(EulerPhi(n), exposant, modulus) where exposant is n where modulus is n > ;
> N := 10^7 ;
> time &and [(F(n) eq n-1)  eq IsPrime(n) : n in [2..N]] ;
true
Time: 75.940
[/color]
  • babsgueye
    babsgueye
    Merci @claude quitté, pour le calcul.
  • babsgueye
    babsgueye
    Bonjour.

    En d'autres termes, avec les trois propriétés :

    1) $P\,\iff\,(T\wedge Q)$,
    2) $\big(T\wedge (\neg P)\big)\,\implies\,(\neg Q)$, et
    3) $\big(Q\wedge (\neg P)\big)\,\implies\,(\neg T)$,

    peut-on logiquement déduire une réponse définitive, (si oui, laquelle) à au moins une des trois conjectures suivantes ?

    a) $T\,\iff\,P$,
    b) $Q\,\iff\,P$, ou
    c) $T\,\iff\,Q$.

    Merci.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    La proposition 1) contient 2) et 3).

    Pour a), $T\Rightarrow P$ mais on n'a pas $P\Rightarrow T$. Ce n'est vrai que si on a Q.
    Pour b), ni l'implication, ni la réciproque ne sont vraies. (toujours à partir de 1) )
    Pour c), ni l'implication, ni la réciproque ne sont vraies. (toujours à partir de 1) )
    Et si Q est vraie, les énoncés b) et c) sont équivalents.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • babsgueye
    babsgueye
    PetitLutinMalicieux a écrit:
    La proposition 1) contient 2).

    Peux-tu me montrer la preuve ?
    PetitLutinMalicieux a écrit:
    Pour a), $T\Rightarrow P$ mais on n'a pas $P\Rightarrow T$.

    Je suis pas très d'accord, parce que justement, mon problème est de montrer que $T\,\implies\,P$.
    Quant à $P\,\implies\,T$, on l'a, car $P\,\implies\,T\wedge Q$.

    Merci.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    2) $(T\wedge \bar P)\ et\ (P \Leftrightarrow (T \wedge Q ) ) \equiv T\bar P ( \bar P \bar T + \bar P \bar Q + TQP )$
    $(T\wedge \bar P) et (P \Leftrightarrow (T \wedge Q ) ) \equiv T\bar P \bar Q$
    Si T est vrai et P est faux, de sorte que $T\bar P$ soit vrai, alors Q est nécessairement faux pour que $\bar Q$ soit vrai et $T\bar P \bar Q$ aussi.
    Donc si on a 1), on a 2).

    3) $(Q\wedge (\neg P))\ et\ (P \Leftrightarrow (T \wedge Q ) ) \equiv Q\bar P ( \bar P \bar T + \bar P \bar Q + TQP )$
    $(Q\wedge (\neg P))\ et\ (P \Leftrightarrow (T \wedge Q ) ) \equiv Q\bar P \bar T$
    Si Q est vrai et P est faux, de sorte que $(Q\wedge (\neg P))$ soit vrai, alors T est nécessairement faux pour que $\bar T$ soit vrai et $ Q\bar P \bar T$ aussi.
    Donc si on a 1), on a 3).

    Pour les deux autres objections, tu as raison. $P\Rightarrow T$. Et T ne force que l'équivalence de P et Q (ce que l'on savait dès le début). Pas plus.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • babsgueye
    babsgueye
    Littéralement, ne devrais-tu pas dire: 2) contient dans 1) ?
  • PetitLutinMalicieux
    PetitLutinMalicieux
    "Contenir" est un verbe transitif. Il doit avoir une cible pour avoir un sens. Et si 2) tient dans 1), c'est bien que 1) contient 2) :-)
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • babsgueye
    babsgueye
    C'est un lapsus. Je voulais dire : 2) contient 1).
    ( 2) contient dans 1) : ce n'est pas du français !).
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Je crois comprendre ce que tu veux dire, dans le sens où si un cas vérifie 1), alors il vérifie 2). Mais, je parlais des propositions, pas des cas auxquels elles s'appliquent. Je n'ai pas l'intention de me battre sur ça. C'est comme si je disais $f(x)=e^{\frac 1 x}$ contient une exponentielle, et que tu me répondes que l'ensemble de définition de f est plus petit que l'ensemble de définition de l'exponentielle.
    Tout ce que je voulais dire, c'est que, si 1) est dans ton paquetage, alors tu as aussi 2).
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • babsgueye
    babsgueye
    Ok Merci.

    Par contre, je pense avoir une preuve logique que : ( 1), 2) et 3) ) implique a), b) et c).
    Je me suis débrouillé en utilisant justement ces notions d'inclusion et des diagrammes de Venn qui ''s'intersectent'', mais que j'arrive pas encore à dessiner avec latex. Donc à plus tard pour soumettre mon raisonnement à la critique.
  • babsgueye
    babsgueye
    IL y a une erreur dans mon argumentation. Comme l'a remarqué @Calli, il est important de quantifier en $n$, sinon avec un raisonnement ensembliste, on fonce direct vers cette erreur.
    Donc c'est vrai @PetitLutinMalicieux, rien de plus !

    Merci.
  • babsgueye
    babsgueye
    Salut.

    J'ai un peu regardé plus arithmétiquement, et je pense bien avoir démontré l'équivalence cherchée.

    A plus.
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 17

GonLirone93i.zitoussim.c1zeste +12 Invités