# Homework Help: Arithmetics problem

1. Jan 5, 2013

### 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?

Last edited: Jan 5, 2013
2. Jan 5, 2013

### 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 am-1= 1 (mod m).

Okay, just try some prime numbers. If m= 5 then am-1= 34= 81= 1 (mod 5). Done!

Perhaps I am misunderstanding your question.

3. Jan 5, 2013

### luciasiti

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

Last edited: Jan 5, 2013
4. Jan 5, 2013

### 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

5. Jan 6, 2013

### haruspex

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

6. Jan 7, 2013

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