6
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Check Carmichael numbers. en.wikipedia.org/wiki/Carmichael_number $\endgroup$ – Aravind Oct 15 '18 at 14:06
  • $\begingroup$ thank you sir. I have just searched for some related info. So, the Carmichael numbers are infinitely many. But is it proved that all of them has no common divisors? If this happens, the proof isn't completed yet $\endgroup$ – ElementX Oct 15 '18 at 14:18
  • 1
    $\begingroup$ Does $\frac{10^{9-1}-1}{9}$ and then $\frac{10^{99-1}-1}{99}$ help? $\endgroup$ – Phil H Oct 15 '18 at 15:13
  • $\begingroup$ @PhilH: Sir, I think that it is only applicable for the case $a = 10$. Do you have a deeper meaning there? Please clarify further. Thank you. $\endgroup$ – ElementX Oct 15 '18 at 15:32
  • 2
    $\begingroup$ For $a = 7, m = 11, 13, 17, 19, 23, 25, 29$.....etc. There appears to be an infinite sequence of $11+2+4+2+4+2$.....etc. A proof would explain why this happens. Not all the numbers are composite but the composite numbers, example $(25)$ repeat. $\endgroup$ – Phil H Oct 15 '18 at 21:42
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Both your examples of m are prime. $3\times8 + 1 = 25$ So $25^{8-1}\equiv 1\ \text{mod}\ 8$ $\endgroup$ – Phil H Oct 18 '18 at 6:29
1
$\begingroup$

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".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.