There are infinitely many composite numbers

[evinda]

Hey again! (Rock)(Wasntme)

I want to show that there are infinitely many composite numbers $n$,for which stands:

$$a^{n-1} \equiv 1 \pmod n$$

So,it must be: $n \mid a^{n-1}-1$

But how can I show that there are infinitely many such $n$ ?? (Thinking)

 

[Opalg]

You know that this result holds when $n$ is prime. Can you make use of that fact to deduce that it must also hold for some numbers that are not prime?

 

[evinda]

You know that this result holds when $n$ is prime. Can you make use of that fact to deduce that it must also hold for some numbers that are not prime?

So could I use the fact that $\displaystyle{ n=p_1^{a_1} \cdots p_k^{a_k}, \text{ where } p_i \text{ are primes and } a_i \geq 1 } $ ? (Thinking)

 

[Deveno]

What is $a$ in this question?

 

[evinda]

What is $a$ in this question?

The only thing we know is that $a^{n-1} \equiv 1 \pmod n$.. (Thinking)

 

[I like Serena]

Hi! (Smile)

The only thing we know is that $a^{n-1} \equiv 1 \pmod n$.. (Thinking)

Isn't that what you need to prove rather than what you know? (Thinking)

Suppose $n=pq$ with $p, q$ primes.
What can you say?
And what do you need? (Wondering)

 

[evinda]

Hi! (Smile)
Isn't that what you need to prove rather than what you know? (Thinking)

Suppose $n=pq$ with $p, q$ primes.
What can you say?
And what do you need? (Wondering)

I want to prove that there exist infinitely many composite numbers $n$,for which:
$$a^{n-1} \equiv 1 \pmod n$$

So,do we suppose that $n=p \cdot q$ and that: $a^{pq-1} \equiv 1 \pmod {pq}$ ?

But...do we know that $n$ is a product of only two primes raised to the power $1$ ? (Thinking) (Thinking)

 

[Deveno]

My point is: is $a$ some FIXED number, or are we trying to prove this for EVERY $a$ AND every $n$?

 

[evinda]

My point is: is $a$ some FIXED number, or are we trying to prove this for EVERY $a$ AND every $n$?

No,it is not a fixed number.. (Thinking)

 

[I like Serena]

I want to prove that there exist infinitely many composite numbers $n$,for which:
$$a^{n-1} \equiv 1 \pmod n$$

So,do we suppose that $n=p \cdot q$ and that: $a^{pq-1} \equiv 1 \pmod {pq}$ ?

But...do we know that $n$ is a product of only two primes raised to the power $1$ ? (Thinking) (Thinking)

If we can find infinitely many $n$ of the form $pq$ for which the statement holds, we're done.
If we can't, we'll have to come up with a new idea.
Just as a line of investigation I'm suggesting to look at $n$ of this form. (Thinking)

So we suppose that $n=p \cdot q$, and we'll try and find values for $p$ and $q$ such that $a^{pq-1} \equiv 1 \pmod {pq}$. The latter is not something we suppose, it's something we try to find.Btw, the meaning of $a$ is ambiguous as Deveno already said. It can mean:

• A specific value that we can choose for which we have to find infinitely many $n$,
• Any specific value for which we have to find infinitely many $n$
• For infinitely many $n$ the statement holds for any $a$.
  In this case we will have to limit $a$ to be co-prime with $n$.

We'll see how much we can cover. (Sweating)

 

[evinda]

If we can find infinitely many $n$ of the form $pq$ for which the statement holds, we're done.
If we can't, we'll have to come up with a new idea.
Just as a line of investigation I'm suggesting to look at $n$ of this form. (Thinking)

So we suppose that $n=p \cdot q$, and we'll try and find values for $p$ and $q$ such that $a^{pq-1} \equiv 1 \pmod {pq}$. The latter is not something we suppose, it's something we try to find.Btw, the meaning of $a$ is ambiguous as Deveno already said. It can mean:

• A specific value that we can choose for which we have to find infinitely many $n$,
• Any specific value for which we have to find infinitely many $n$
• For infinitely many $n$ the statement holds for any $a$.
  In this case we will have to limit $a$ to be co-prime with $n$.

We'll see how much we can cover. (Sweating)

So,we know that $a^{pq-1} \equiv 1 \pmod {pq}$ and as $(p,q)=1$,it must be:
$$a^{pq-1} \equiv 1 \pmod {p} \text{ and } a^{pq-1} \equiv 1 \pmod {q}$$

But...what else do we know? (Thinking) (Thinking)

 

[I like Serena]

So,we know that $a^{pq-1} \equiv 1 \pmod {pq}$ and as $(p,q)=1$,it must be:
$$a^{pq-1} \equiv 1 \pmod {p} \text{ and } a^{pq-1} \equiv 1 \pmod {q}$$

But...what else do we know? (Thinking) (Thinking)

How about $a^{\phi(pq)}\equiv 1 \pmod{pq}$? (Thinking)

 

[evinda]

How about $a^{\phi(pq)}\equiv 1 \pmod{pq}$? (Thinking)

Isn't it $\phi(p \cdot q)=\phi(p) \cdot \phi(q)=(p-1)(q-1)$?
How can we use this? (Thinking)

 

[I like Serena]

Isn't it $\phi(p \cdot q)=\phi(p) \cdot \phi(q)=(p-1)(q-1)$?
How can we use this? (Thinking)

So you know for sure that for any prime $p,q$:
$$a^{(p-1)(q-1)} \equiv 1 \pmod{pq}$$
that is, if $(a, pq)=1$.

And you want to find some $p,q$ such that:
$$a^{pq-1} \equiv 1 \pmod{pq}$$

Perhaps you can combine them to make it simpler. (Thinking)

 

[Opalg]

Hey again! (Rock)(Wasntme)

I want to show that there are infinitely many composite numbers $n$,for which stands:

$$a^{n-1} \equiv 1 \pmod n$$

So,it must be: $n \mid a^{n-1}-1$

But how can I show that there are infinitely many such $n$ ?? (Thinking)

This question is more complicated than I first thought. Firstly, if $a$ is allowed to depend on $n$, then for any odd number $n$ we can take $a = n-1$. The binomial expansion of $(n-1)^{n-1}$ shows that $(n-1)^{n-1} \equiv 1 \pmod n.$

For a fixed value of $a$ we seem to be in the realm of Fermat pseudoprimes, where things become very much more complicated. For each $a$, there are infinitely many pseudoprimes $n$ (in other words, non-primes such that $a^{n-1} \equiv 1 \pmod n$). For $a=2$, the smallest case occurs when $n = 341$. In that case, $341 = 11\times 31$ is not prime, but apparently $2^{340}\equiv1 \pmod{341}.$