1k views

### If the order of a number (mod n) equals n-1 then n is prime? [duplicate]

I have trouble in understanding the last part of the sufficiency proof of Pépin´s Test (https://en.wikipedia.org/wiki/Pépin%27s_test). "In particular, there are at least least F_{n}-1 numbers below ...
400 views

### Prove that $a^{n-1} \equiv 1 \pmod n$ and $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$ implies $n$ is prime [duplicate]

Let $a$ and $n\ge3$ be integers. Suppose that $a^{n-1} \equiv 1 \pmod n$, while $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$, and I want to show that $n$ is prime. First of ...
• 1,451
1 vote
47 views

• 1,713
1 vote
696 views

I am trying to prove by contrapositive, i.e. If $m$ is composite, then for all $a \in \mathbb{Z}$, either $a^{m-1} \not \equiv 1 \pmod{m}$ or $\exists k: 0 < k < m-1$ where $a^k \equiv 1 \pmod{... • 425 1 vote 3 answers 161 views ### If there is an$a\in\mathbb{Z}$with$a^{n-1}\equiv 1\mod n$but$a^{\frac{n-1}p}\not\equiv 1$for all primes$p\mid n-1$, then$n$is a prime Let$n\in\mathbb{N}$with$n\ge 3$and$a\in\mathbb{Z}$such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ ... • 13.4k 0 votes 0 answers 298 views ### Disproving the converse of Fermat's Little Theorem Fermat's Little Theorem states that If$p$is a prime and$a \in Z$with$gcd(a,p)=1$then$a^{p-1} \equiv 1 \mod p$from this I take to the converse to be the statement that if$a^{p-1} \equiv 1 \...
• 449
1 vote
fermat test says : if $a^{N-1} \equiv 1 \pmod N$, then N is probably prime number, but according to pocklington primality test if: $3^{N-1} \equiv 1 \pmod N$, then N is proven prime, where $N=2p+1$...
Fermat's little theorem states that if $p$ is prime, then $\forall a\in\mathbb N \quad a^p\equiv a \quad \text{mod} \quad p$. Is the converse true ?