0

For every positive integer $a$, find a composite number $n$ such that $n|a^n -a$.

Solution:

We have

$ a^n - a$

$ = a[a^{(n-1)}-1]$

If a=n, then $n|a^n -a$

Is this the way to do it or do I need to do it in another way?

Anwesa Roy
  • 49
  • 1
    Since your suggestion is to use $n=a$ and the task is finding a composite number $n$, the obvious question would be what to do if $a=1$ or $a$ is a prime. –  Oct 12 '21 at 15:14
  • @SaucyO'Path Seems like I am stuck. Can you please help. – Anwesa Roy Oct 12 '21 at 15:27
  • If $n$ is a Carmichael number and $\gcd(a,n)=1$ , then we have $a^n\equiv a\mod n$. So, we only have to find a Carmichael number $n$ coprime to $a$, this should be possible no matter what $a$ is. I am however not sure how to prove that. If there are infinite many positive integers $k$ such that $6k+1,12k+1,18k+1$ are all prime , we are done, unfortunately this is not known. – Peter Oct 12 '21 at 16:32

1 Answers1

4

You're done when $a$ is composite itself. When $a=1$, just pick any composite $n$. When $a$ is an odd prime, let $n=2a$, then clearly $a^n-a$ is even i.e. $2\mid a^n-a$, and obviously $a\mid a^n-a$, as $\gcd(2,a)=1$, we have $2a\mid a^n-a$.

$a=2$ is tricky. I did a computer search, and $n = 341 = 11 \cdot 31$ is the minimal solution.

As commented below, this is the smallest Fermat psuedoprime to base $2$. Wikipedia mentioned a method to construct them by Cipolla, with $341$ given as an example.

Just a user
  • 14,899
  • Yep. You just re-discovered the smallest Fermat pseudoprime to base $2$. –  Oct 12 '21 at 17:21