Suites et Nombres premiers

[nodgim]

Hum....et le contre-exemple que j'ai écrit ?

[anthony_unac]

Sauf erreur:
u13 = 1 [5] et 1 [4] (la puissance de 13 est 0 [4], donc Fermat dit que a^4 = 1 [5])
u14 [5] = 4 ^ (1+4k) = 4 [5]
donc v13 = 0 [5].

Bonjour nodgim,
avec
Autrement dit est divisible par :
Il en découle que et
Conclusion :
J'ai du louper un truc quelque part

[anthony_unac]

Autant pour moi c'est l'étape du petit théorème de Fermat que j'ai zappé.
Votre contre exemple est presque juste
Je vais détailler votre raisonnement :
avec entier naturel donc d'après le petit théorème de Fermat.
Mais malheureusement qui n'est pas premier !
Votre exemple ne contredit donc pas la proposition : "Pour tout tel que est premier, est premier"

[nodgim]

Ah oui zut...

[nodgim]

J'en ai tout de même un autre en réserve, et qui marche cette fois il me semble : v15
En effet, u15 = 1 [17] et 1 [16]
u16 = 16 [17]
donc v15 = 0 [17]
et 15 + 16 = 31 est premier.

[Skullkid]

Bonjour, sauf erreur n = 33 est un contre-exemple : en travaillant modulo 5 car est impair et est divisible par 4.

Edit : grillé par nodgim et son n plus petit

[anthony_unac]

Bonsoir,
Merci à vous deux pour vos propositions, je confirme que est divisible par , en revanche je ne comprends pas votre façon de faire nodgim. Pouvez vous expliciter tout ça

[nodgim]

Euh...à peu près la même que Skullkid.

L'énigme est trompeuse, puisqu'elle nous invite à regarder du coté de Fermat avec ce 2n+1, ce qui est vrai, mais il ne faut pas regarder le nb premier n + (n+1) mais un autre nombre premier.

En fait, on peut généraliser, en disant que v(2^n - 1) est toujours divisible par 2^n+1 si celui ci est premier. Sauf pour les petits valeurs initiales qui ne comportent pas assez de puissances paires.

u(2^n-1) possède une puissance paire supérieure à 2^n dans le cas général. Or on sait par Fermat que a^k(p-1) = 1 modulo p. Donc u(2^n-1) vaut 1 modulo 2^n + 1 si celui ci est premier. De plus, u(2^n-1) est un carré, et (2^n-1)^2j vaut 1 modulo 2^n (carré de -1 )

u(2^n-1) = 1 [2^n+1] et 1 [2^n]

u(2^n) a pour puissance u(2^n-1) qui vaut 1 modulo [2^n].
(2^n) ^ (1 + k*2^n) = 2^n [2^n+1] car (2^n) ^ (k*2^n) = 1 [2^n+1 premier]

D'où u(2^n)= 2^n [2^n+1]

Et donc v (2^n-1) = 1+ 2^n = 0 [2^n+1]

[Ben314]

Salut,
Je viens de vaguement regarder le thread et je ne suis pas d'accord avec ça :

Pour prendre un exemple simple, si on prend la suite .
...
n'implique pas : , car : n'implique pas :

Certes, vu que l'ensemble des est contenu dans , la véracité d'une proposition du style (souvent facile à établir en étudiant les variations de la fonction )
entrainerait la véracité de la proposition .
Mais, très clairement, la réciproque est fausse donc le raisonnement que tu fait, à savoir de considérer que Q est fausse vu que P est fausse est erroné.

Vu la tête de la suite : , la proposition est vrai pour tout entier k et donc indiscutablement, la proposition est vraie vu que (Vrai => Vrai) est Vrai.

[Skullkid]

Pour ma part je suis parti des petits modulos pour essayer de trouver, à tâtons, un contre-exemple. On se rend assez vite compte que rien n'est possible modulo 3, donc je suis passé à 5, et par chance j'ai pas eu besoin d'aller plus loin. Comme nodgim, je me suis en fait retrouvé avec une suite de candidats contre-exemples, à savoir les qui sont tous divisibles par 5. Il suffit alors de prendre un k tel que 2n+1 = 20k+7 soit premier (et donc en fait j'aurais pu me contenter de ).

Par rapport au post de Ben314, en effet l'implication est vraie, on en revient comme souvent à la confusion entre l'implication et le modus ponens, ou entre l'implication et le "donc". Ce que Pseuda voulait dire c'est qu'on ne peut pas déduire (par modus ponens) des seuls faits que et , mais cela n'a en effet rien à voir avec la véracité ou non de l'implication .

[anthony_unac]

Bonsoir,
@ Ben Je ne vais pas commencer à argumenter (car je n'ai pas le niveau requis pour ça) mais il me semble que ma synthèse revue et corrigée indique la direction du bien fondé (communément admis par l'ensemble des intervenants du forum). Si vous pensez qu'il y a une faute évidente qui aurait échapée à l'ensemble des participants n'hésitez pas à soulever précisément et clairement cette faute
@ Nodgim Pourquoi êtes vous aussi avare en explications concernant votre raisonnement ? Lachez un peu de leste que diable si vous êtes certain de vous, qu avez vous à perdre ?

[nodgim]

@ anthony_unac :
Je ne suis pas avare en explications, ce n'est pas l'esprit en tout cas, mais il est vrai que je suis médiocrement pédagogue. Ce que j'ai écrit dans le msg 1118 ne suffit pas ?

[anthony_unac]

Bonjour,

Voici un contre exemple qui n'utilise pas les outils "congruences" et "petit théorème de Fermat" mais deux propriétés toutes simples :
Pour tout entier naturel , et
avec


En admettant ces deux propriétés, il vient le contre exemple suivant :

avec :

avec un entier naturel
donc :


Conclusion :
n'est pas premier et constitue donc un contre exemple à la proposition.

Si vous avez compris "la mécanique" de ce contre exemple alors vous pouvez en fabriquer des milliers et des milliers d'autres :
Pour tout entier naturel , et (supérieur à ) tels que est premier et , n'est pas premier.
NB: Je remercie au passage l'intervenant Bolza qui m'a très largement aiguillé vers cette solution

[nodgim]

ça marche en effet.
Mais il me semble que tu limites trop la forme de n. Je ne pense pas qu'il soit indispensable que n soit impair. Si n est de la forme a^b avec pgcd (a;b) ni 1 ni une puissance de 2, ça doit marcher.
En revanche, pour avancer qu'il y a des milliers et des milliers de solutions, c'est sûrement vrai, mais pas forcément....

[anthony_unac]

Si est pair, le même mécanisme se produit mais la forme de est différente :

avec

et


Si avec et entiers naturels et si avec entier naturel alors n'est pas premier.

Mais attention ceci n'est qu'un moyen parmi tant d'autres de débusquer des contre exemples

[Pseuda]

Salut,
Je viens de vaguement regarder le thread et je ne suis pas d'accord avec ça :

Pour prendre un exemple simple, si on prend la suite .
...
n'implique pas : , car : n'implique pas :

Certes, vu que l'ensemble des est contenu dans , la véracité d'une proposition du style (souvent facile à établir en étudiant les variations de la fonction )
entrainerait la véracité de la proposition .
Mais, très clairement, la réciproque est fausse donc le raisonnement que tu fait, à savoir de considérer que Q est fausse vu que P est fausse est erroné.

Vu la tête de la suite : , la proposition est vrai pour tout entier k et donc indiscutablement, la proposition est vraie vu que (Vrai => Vrai) est Vrai.

Bonsoir,

De retour après une panne internet.

En logique mathématique, je suis d'accord pour dire qu'avec la suite définie par et , la proposition est vraie.

Mais le but est justement de montrer que la proposition suivante est fausse : " vraie n'implique pas vraie, donc vraie, est faux". C'est-à-dire qu'on peut avoir vraie, bien qu'on ait le "n'implique pas". Pour trouver un contre-exemple, il faut donc bien créer un paradoxe, ou une erreur en quelque sorte.

De manière générale, si on ne sait rien de la suite , n'implique pas , donc pour cette suite, n'implique pas . Et pourtant, pour cette suite, justement pour tout n.

Evidemment si on sait que est vraie, on n'en parle plus. Mais là, on se place dans l'hypothèse où on ne le sait pas encore.

En d'autres termes, je dirais qu'on ne peut pas utiliser la conclusion pour démontrer les hypothèses.

[Doraki]

Moi j'ai rien compris à la discussion

Hérédité : On suppose la proposition vraie au rang vraie mais n'implique pas vraie.
est divisible par
n'est pas divisible par car n'est pas divisible par .
n'implique pas donc la proposition est fausse sauf que ce raisonnement lui même est faux !

ça c'est du grand n'importe quoi

"je n'ai pas réussi à montrer A => B"
ce n'est pas équivalent à "A => non B", ni à "non (A => B)", et d'ailleurs ça n'a même pas de sens mathématique.