# Prime numbers in Fermat's little theorem

Consider prime numbers $a$ and $p$.

It is known according to Fermat's little theorem (FLT) that the congruence $a^{p-1} \equiv 1 \pmod {p}$ holds for any prime $a$ and $p$.

From this we have that there are infinitely many numbers of form $a^m$ which are congruent to $1$ as any power $(a^{p-1})^k$ is congruent to $1$ if only $a^{p-1}$ is congruent.

The question arises however whether a number $m=p-1$ appearing in FLT is the smallest number (obviously excluding $a^0=1$) which satifies $a^m \equiv 1 \pmod {p}$ ?

I've made some experimental analysis taking into account powers of $a=2$ and sequence of prime numbers $p=5,7,11,13,17, 19 , \dots$.

I will name prime numbers $p$ for which equality above is satisfied when there is no less number $m$ than $p-1$ that $2^m \equiv 1 \pmod {p}$ proper FLT prime numbers - if it happens that however there is a number $m<p-1$ when $2^m \equiv 1 \pmod {p}$ is satisfied I will name such number $p$ improper FLT number (if there is more official terminology let me know) and number $m$ initial number for the given $p$.

Having made calculations I received following numbers $p$ for powers of two congruent to $1 \pmod {p}$:

Proper LFT numbers: $5(4),11(10),13(12),19(18),29(28),37(36),53(52),59(58) \dots$

Improper LFT numbers: $7 (3), 17 (8), 23(11), 31(5),41(20),43(14), 47(23)\dots$

Here in brackets smallest exponents $m$ (named as initial numbers) for satysfying formula $2^m \equiv 1 \pmod {p}$ are given. For example $2^8\equiv 1 \pmod {17}$.

Evidently initial numbers for improper FLT numbers are divisors of $p-1$ what is intuitively expected but why exactly such value not other ? (see $5$ for $31$, not for example $10$ or see $14$ for $43$ not $7$) it's hard to say.

My question:

• is it any method to discern proper and improper FLT numbers?
• if we are able to recognize that a given prime number is FLT improper can we also say what is an initial number associated with it?
• Perhaps you like this exploration of the same question like yours but a little broader go.helms-net.de/math/expdioph/CyclicSubgroups_work.pdf – Gottfried Helms Oct 18 '17 at 12:47
• @GottfriedHelms Thank you very much, very interesting paper. Here it is even used the abbrevation FLT but .. for Fermat's Last Theorem :) – Widawensen Oct 19 '17 at 6:08
• @GottfriedHelms Coincidentally abbreviation FLT fits to Fermat's Little Theorem and Fermat's Last Theorem at the same time. Maybe solution for this terminology ambiguity would be to use name Flitt and Flast for numbers in these theorems. – Widawensen Oct 20 '17 at 8:48
• Dear Widawensen - that is a really scurrile and funny idea! I'll consider this for some nice moment.... – Gottfried Helms Oct 20 '17 at 9:51

You are investigating whether the number $2$ is a "primitive root" modulo $p$. Every number $a=1,2,\ldots,p-1$ has an "order" mod $p$, which is the smallest power of $a$ that is congruent to $1$ modulo $p$. A primitive root is a number whose order is $p-1$. The fact that every prime number has a primitive root is a non-trivial result.

Once we know that every prime has a primitive root, how do we predict which number(s) will be primitive roots, and which ones won't? This is hard, and there isn't a simple answer. We can say how many primitive roots there are for a given prime $p$, and once we find one, it's a simple matter to list the others. However, finding the first one is not something that we have a formula for.

I recommend reading up on primitive roots, and if you know some abstract algebra, studying the structure of the "units group" modulo $p$ (or, for even more fun, modulo $n$ for any natural number $n$.) Here's a starting point: Primitive root on Wikipedia

In any event, keep reading and asking great questions like this one about number theory! There is no limit to the joy you will find there. :)

• There is no formula ? I'm a little disappointed.. my knowledge of abstract algebra is very basic... I was thinking that this kind of problem belongs rather to the number theory ... thank you for the encouragement ... and starting point.. – Widawensen Oct 17 '17 at 14:41
• Yes, I know that... from this follows that are infinitely many such congruent to 1 numbers... however sometimes this initial number is not a number calculated from FLT (p-1) but some divisor of p-1 – Widawensen Oct 17 '17 at 15:06
• The numbers that are congruent to $1$ for a power less than $p-1$ are not primitive roots. Neither $2$ nor $3$ is a primitive root for $p=23$, but $5$ is one. You have discovered that $2$ is a primitive root for $p=5, 11, 13, 19, \ldots$ – G Tony Jacobs Oct 17 '17 at 15:07
• Whew.... I really don't know. Pretty sure it's not an area of current research, although there are related conjectures that people are working on. Using your terminology, for any $a>1$ that is not a perfect square, are there infinitely many primes that are LFT-proper? Artin's conjecture surmises that there are. – G Tony Jacobs Oct 17 '17 at 15:15
• Now I guess it's time for me to study the paper from the starting point... maybe then I will add something to this problem.. – Widawensen Oct 17 '17 at 15:17