Solving Arithmetics Problem: Find m Number for a^(m-1) ≡ 1 mod m

[luciasiti]

Hi everyone
I'm having difficulty in proving the following problem
Give $a\in \mathbb{Z}$ and $a \ne 0$. Prove that: there exist infinitely many composite numbers m such that $a^{m-1}\equiv 1 mod m$
I tried to find m number, which is satisfied with problem requirement, but I still haven't found it.
Can you help me find m number?
Thanks for your help!

 

[HallsofIvy]

You are trying to prove there exist infinitely many and you cannot find even 1? You need to talk to your teacher about this!

Suppose a= 3. Then you want to find prime m such that a^m-1= 1 (mod m).

Okay, just try some prime numbers. If m= 5 then a^m-1= 3⁴= 81= 1 (mod 5). Done!

Perhaps I am misunderstanding your question.

 

[luciasiti]

You are trying to prove there exist infinitely many and you cannot find even 1? You need to talk to your teacher about this!

Suppose a= 3. Then you want to find prime m such that a^m-1= 1 (mod m).

Okay, just try some prime numbers. If m= 5 then a^m-1= 3⁴= 81= 1 (mod 5). Done!

Perhaps I am misunderstanding your question.

Thank you. But, in this problem, m is not prime number, m is composite number and a is an any integer.

 

[haruspex]

If m is odd then a=m-1 is a trivial solution. Other solutions are quite sparse. In the form a;m I found
4;15, 4;85, 4;9, 15;85, 7;77, 8;21, 8;45, 8;63, 8;105, 8;65, 11;15, 11;45, 15;49, 16;51, 16;85, 16;91, 18;115, 19;105, 20;85, 21;69, 27;33, 31;33, 31;77, 32;93, 34;77, 35;99, 37;55, 38;115

 

[haruspex]

If m is odd then a=m-1 is a trivial solution. Other solutions are quite sparse. In the form a;m I found
4;15, 4;85, 4;9, 15;85, 7;77, 8;21, 8;45, 8;63, 8;105, 8;65, 11;15, 11;45, 15;49, 16;51, 16;85, 16;91, 18;115, 19;105, 20;85, 21;69, 27;33, 31;33, 31;77, 32;93, 34;77, 35;99, 37;55, 38;115

Typo: should have been 4;91, not 4;9.
Have now found a general solution for a even: set m = a²-1. Might be extensible to an infinite set of m values somehow.

 

[Joffan]

The m values are the Fermat pseudoprimes to base a. There are an infinity of them but they are generally not very dense; much less dense than primes.

A proof is here: http://primes.utm.edu/notes/proofs/a_pseudoprimes.html - you aren't going to stumble on this by trial and error.