Linked Questions

0 votes
1 answer

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 (épin%27s_test). "In particular, there are at least least F_{n}-1 numbers below ...
Luis Gimeno Sotelo's user avatar
2 votes
1 answer

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 ...
b_pcakes's user avatar
  • 1,451
1 vote
0 answers

On slightly stronger form of the converse of Fermat's little theorem [duplicate]

Fom wiki Fermat's little theorem, the theorem is as follows: If there exists an integer $a$ such that $ a^{p-1}\equiv 1\pmod p $ and for all primes $q$ dividing $p − 1$ one has ${\displaystyle a^{(p-1)...
miket's user avatar
  • 1,069
25 votes
2 answers

$\bmod n\!:\ a^n \equiv 1\!\iff\! $ order of $a$ divides $n,\,$ e.g. when $\,n = \phi(m)$

How can I show that the order of an element modulo $m$ divides $\phi(m)$? I know that if $a$ and $m$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod m$ is its ...
wjmolina's user avatar
  • 6,140
5 votes
2 answers

Converse of Fermat's Little Theorem.

If $a^n\equiv a \pmod n$ for all integers $a$, does this imply that $n$ is prime? I believe this is the converse of Fermat's little theorem.
IntegrateThis's user avatar
4 votes
2 answers

Why is $120^{128}+1$ a prime number

Wolfram Alpha says that the number $120^{128}+1$ is prime. I wonder if that is in fact true, and if so, what is an argument for it. Thank you for your interest!
orangeskid's user avatar
  • 53.4k
3 votes
3 answers

If $a^{n-1} \equiv 1 \pmod{n}$, can we say that $(a,n) = 1$?

If $a^{n-1} \equiv 1 \pmod{n}$, can we say that $(a,n) = 1$? If not, what conditions do we need to make this argument true? Any idea? Thanks,
roxrook's user avatar
  • 11.9k
1 vote
3 answers

Explain why 67 is prime based on the fact that order of 2 mod 67 is 66

Without using the fact that 67 is prime, show that the order of 2 mod 67 is 66. Explain why this result proves that 67 is prime What I understand: The order of 2 in $\mathbb{Z}_{67}$(or mod $67$) $ =...
Arvin's user avatar
  • 1,713
1 vote
2 answers

$m$ is prime if some integer has order $m-1$ modulo $m$

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{...
StockComCat's user avatar
1 vote
3 answers

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$$ ...
0xbadf00d's user avatar
  • 13.4k
0 votes
0 answers

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 \...
cb7's user avatar
  • 449
1 vote
2 answers

is there any deterministic versions of fermat test except this one?

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$...
عبد الرحمن رمزي محمود's user avatar
1 vote
0 answers

Converse of Fermat's Little Theorem [duplicate]

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 ?
James Well's user avatar
  • 1,199