Pseudo-premiers
dans Arithmétique
Bonjour, svp comment monter que si n est pseudo-premier alors 2^n-1 est aussi pseudo-premier ??
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Soit $n$ "pseudo-premier"
$ \bullet\:$ Alors $n$ n'est pas premier, donc $2^n -1$ est divisible par $2^d-1$ (où $d$ désigne un diviseur positif de $n$, différent de $1$ et de $n$) et ainsi: $$\boxed{ 2^n-1\text{ n'est pas premier}}$$.
$\bullet\:$ D'autre part, $\:\:2^n \equiv 2 \mod n$, donc: $\:\exists k \in \N$ tel que : $\:2^n- 2 = kn$.
On déduit alors, $\mod 2^n -1,\:\:$ les congruences suivantes: $2^n \equiv 1 \implies 2^{kn} =1 \iff 2^{2^n-2} \equiv 1$, puis: $$ \boxed{ 2^{2^n-1} \equiv 2 \mod 2^n-1}$$
Aussi comment déduite qu'il y a une infinité de nombres pseudo premier en utilisant n pseudo premier implique 2^n-1 l'est aussi
1) Tu devrais apprendre à utiliser les parenthèses : "(2^2^n-1)" est-il $(2^2)^n-1=4^n-1$ ou $2^{2^n}-1$ ?
2) en regardant les premières valeur de n (1, 2, 3), tu devrais pouvoir facilement répondre à ta question.
Cordialement.
je n'arrive pas a en déduire qu'il y a une infinite de nombre pseudo premier impair avec (n pseudo premier alors 2^n-1 l'est aussi)
Je note: $\forall n \in \N,\: u_n = 2^{2^n}-1.\:\:$ Soit $n>1$.
$\bullet$Alors $u_n>3$ et $u_n \equiv 0 \mod 3:\:\:\:\boxed{ \forall n \in \N,\:\:u_n\:\text {est premier}\:\iff n=1}$
$\bullet$ D'autre part: $u_n \equiv 3 \mod 4 $ donc $2^{u_n} \equiv 3 \mod 5$. Ainsi $2^{u_n} \not \equiv 2 \mod 5 \quad (\star)$.
Mais on a également la congruence: $ u_n \equiv 0 \mod 5$, qui avec $\:(\star)$, entraine: $\:\:\: 2^{u_n} \not \equiv 2 \mod u_n$.
$$\boxed {\forall n \in \N^*,\:\: u_n \:\text{n'est pas pseudo-premier}}$$
$\bullet$ J'ai entendu dire qu'il existait des "pseudo-premiers". Soit $a$ le plus petit d'entre eux et $(v_n)_{n\in \N} $ la suite définie par: $\:\:v_0 =a, \quad \forall n \in \N,\: v_{n+1} =\displaystyle 2 ^{v_n}-1.\:\:\boxed{\:(v_n)_n\:\text{est une suite infinie de "pseudo-premiers"}}$
Et c'est reparti pour une petite valse des exposants.
$\forall n \in \N,\:\:\: F_n = 2^{2^n}+1.$
$ 2^{2^n} \equiv -1 \mod F_n \implies \Big (2^{2^n} \Big) ^{2^{2^n-n}} \equiv 1 \mod F_n \iff 2^{F_n-1} \equiv 1 \mod F_n \iff 2^{F_n} \equiv 2 \mod F_n$.
$$\boxed{\forall n \in \N,\:\: F_n\: \text{ est premier ou "pseudo-premier"}}$$