$\begingroup$

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?

$\endgroup$ 4

1 Answer

$\begingroup$

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. :)

$\endgroup$ 18

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy