Linked Questions
13 questions linked to/from How to prove Lucas's Converse of Fermat's Little Theorem without using primitive root?
0
votes
1
answer
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 ...
2
votes
1
answer
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
0
answers
47
views
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)...
- 1,069
25
votes
2
answers
11k
views
$\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 ...
- 6,140
5
votes
2
answers
4k
views
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.
- 3,738
4
votes
2
answers
239
views
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!
- 53.4k
3
votes
3
answers
228
views
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,
- 11.9k
1
vote
3
answers
303
views
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$) $ =...
- 1,713
1
vote
2
answers
696
views
$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{...
- 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
2
answers
107
views
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$...
1
vote
0
answers
103
views
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 ?
- 1,199