Fermat's little theorem got cracked?

Number Theory Level 2

If:

$\large a^{n-1} \equiv 1 \pmod n$ and $\large \text{gcd}(a,n)=1$

Is it necessarily the case that $n$ is prime ?

No This is too complicated Yes I don't know

2 solutions

Michael Mendrin
Aug 27, 2018

$11^{14} \equiv 1 \pmod {15},$ but $15 = 3\cdot 5.$

I suppose it is "possible" to say that $n$ is prime, and from your example also "possible" to say it is not prime. Just wondering if "Is it necessarily the case that $n$ is prime?" would be a less ambiguous phrasing of the question. (I could file a report but staff never gets to them anymore.)

cc @Syed Hamza Khalid

Brian Charlesworth - 2 years, 9 months ago

the wording should be how you've suggested it

Michael Mendrin - 2 years, 9 months ago

Yeah that's true. I will edit the problem.

Syed Hamza Khalid - 2 years, 9 months ago

Syed Hamza Khalid
Aug 26, 2018

The answer is no; for instance, $2^{340} \equiv 1 \pmod {341},$ but $341 = 11\cdot 31.$

You can add a numberphile reference here.

Hans Gabriel Daduya - 2 years, 9 months ago

Yeah, that's true. Why don't you post it as your solution?

Syed Hamza Khalid - 2 years, 9 months ago

Fermat's little theorem got cracked?

2 solutions

0 pending reports