Prove that there are infinitely many composite number $m$ such that $a^{m-1} - 1$ is divisible by $m$

Question

Problem: Given a positive integer $a$. Prove that there are infinitely many composite number $m$ such that $(a,m) = 1$ and $a^{m-1} - 1$ is divisible by $m$

It is well known that $a^{\varphi (m)} \equiv 1 (\text{mod } m) $ for all $m$ such that $(a,m) = 1$. However I'm not sure how I can use this result (is it usable?) to solve the prementioned problem.

Should there be infinitely many composite numbers $m$ such that $\varphi (m) \mid m-1$, the problem is immediately solved. However, I found out that there aren't even any known number that sastifies what I desire (Lehmer's totient problem).

I attempted to give $a$ a certain value, e.g $7$, and try to build infinitely many composite numbers $m$. So far, I found out that $7^{24} \equiv 1 (\text{mod } 25)$, but that's it. I can't even solve the problem for a special case, let alone insights for the general case.

Currently, I'm stuck without any directions. Any help is grealt appreciated

Answer 1

There can be infinitely many solutions for congruence $a^{m-1}≡1 \mod m$ if $a= km+1$,(this shows that a and m are co-primes) because with this condition we may write:

$a≡1 \mod m$⇒ $a^{m-1}≡1^{m-1}\mod m≡1\mod m$

Now for a given m There is always a number like $a=km+1$ and in contrary for a given a there is a number like m such that $km+1=a$. If m is composite then each factor of it satisfies the relation; in fact we have:

If $a^{m-1}≡1 \mod m$, and $m= \alpha\times \beta\times \theta...$ then following congruence hold:

$a^{\alpha-1}≡1 \mod m$

$a^{\beta-1}≡1 \mod m$

$a^{\theta-1}≡1 \mod m$

The general argument is to claim that the necessary and sufficient condition for congruence be hold is that $a-1$ and m must have a common divisor, in fact we have:

$(a-1)^m≡1\mod a≡1\mod m$

Examples:

$61^{20-1}≡1\mod 20$

$106^{21-1}≡1\mod 21$

$27^{52-1}≡1\mod 52$

In this example $a<m$ and congruence holds because $a-1$ and m have the common divisor 26.

Answer 2

I eventually came up with a similar result as sirous. But to make sure "m" is always composite choose a prime "a".

For $a = 13$, choosing a factor of $13-1 = 12$, say $6$ will give us $\frac{(13)^5-1}{6}$

The reason $(13)^5-1$ is divisible by $6$ is:

$(13)^5-1 = (12+1)^5-1$

$= 12^5+5(12)^4+10(12)^3+10(12)^2+5(12)+1-1$

$= 12^5+5(12)^4+10(12)^3+10(12)^2+5(12)$

whereby all the terms are multiples of $12$ hence divisible by $6$.

For an infinite number of primes for "a" there are an infinite number of composites for "m".