Find all positive integers $n$ satisfying the following conditions simultaneously: (a) the number of positive divisors of $n$ is not a multiple of $8$; (b) for all integers $x$, we have \[x^n \equiv x \mod n.\] Proposed by usjl
Problem
Source: 2023 Taiwan Mathematics Olympiad
Tags: Taiwan
USJL
08.02.2023 09:33
Remark: As the title suggests, this is can be solved by a really well-known statement, basically saying that the Carmichael number is square-free has at least three distinct prime factors.
CrazyInMath
08.02.2023 11:28
Made a small mistake in the test, might cost me TST qualification
It's easy to see $1$ and all prime $p$ works, let's prove nothing else works.
First, let's consider there exists a prime $p$ where $p^2\mid n$. Since $x^n\equiv x\pmod{n}$, we have $$x^n\equiv x\pmod{p^2}.$$However, this can't work since we can take $x=p$ and we will have $p^2\mid p^n$, which is not what the problem wanted.
Now we know that $x$ is square free, the only case we need to consider now is $x=pq$ where $p$ and $q$ are distinct primes. take a primitive root mod $p$ and call it $g$, we have $g^{pq}\equiv g \pmod{p}$, so we have $q\equiv 1\pmod {p-1}$. Using the same way we have $p\equiv 1\pmod{q-1}$. Now WLOG let $p>q$, we have $q\leq p-1$, but $q\equiv 1\pmod {p-1}$ gives us $q=1$ which is not a prime, contradiction.
So the only answers are 1 and all prime $p$.
Cali.Math
19.03.2023 21:47
Here is my solution: https://calimath.org/pdf/TaiwanMO2023-2.pdf And I uploaded the solution with motivation to: https://youtu.be/wXvnrxEsuxI
CrazyInMath
26.03.2023 08:19
CrazyInMath wrote: Made a small mistake in the test, might cost me TST qualification
It's easy to see $1$ and all prime $p$ works, let's prove nothing else works.
First, let's consider there exists a prime $p$ where $p^2\mid n$. Since $x^n\equiv x\pmod{n}$, we have $$x^n\equiv x\pmod{p^2}.$$However, this can't work since we can take $x=p$ and we will have $p^2\mid p^n$, which is not what the problem wanted.
Now we know that $x$ is square free, the only case we need to consider now is $x=pq$ where $p$ and $q$ are distinct primes. take a primitive root mod $p$ and call it $g$, we have $g^{pq}\equiv g \pmod{p}$, so we have $q\equiv 1\pmod {p-1}$. Using the same way we have $p\equiv 1\pmod{q-1}$. Now WLOG let $p>q$, we have $q\leq p-1$, but $q\equiv 1\pmod {p-1}$ gives us $q=1$ which is not a prime, contradiction.
So the only answers are 1 and all prime $p$.
It actually cost me TST qualification, so take this as my revenge.
Iveela
02.02.2024 20:53
The answers are $1$ and all primes. The verification is easy, so we prove that these are the only solutions. We begin by showing that $n$ is squarefree. Let $p$ be an arbitrary prime divisor of $n$. Substituting $x=p$ gives us $p^n \equiv p \pmod{n}$, so we have $\gcd(p^n, n)=\gcd(p, n)$. It follows that $p^2 \nmid n$. Now, recall that the number of positive divisors of an integer $n$, where $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ is its prime factorization is $(\alpha_1-1)(\alpha_2-1) \dots (\alpha_k-1)$. Combined with the fact that $n$ is squarefree, this tells us that $n$ has at most $2$ prime divisors. We may only consider the case where $n$ has exactly $2$ prime divisors. Let $p > q$ be these primes. Then, $x^{pq} \equiv x^q \equiv x \pmod{p}$ for all integers $x$, which cannot be true by Lagrange's theorem. $\blacksquare$
Assassino9931
13.09.2024 00:36
Note that $1$ and all primes work by Fermat's little theorem (and as a prime has only $2$ divisors). We prove that nothing else works. Note firstly that $n$ must be squarefree -- indeed, if $p^2$ divides $n$, then $p^n \equiv p \pmod {p^2}$ is impossible, as $p^2$ does not divide $p$. Since the problem requires the number of divisors of $n$ to not be a multiple of $8$, it remains to consider $n=pq$ for primes $p>q$. Let $g$ be a primitive root mod $p$. We have $g^{pq}\equiv g \pmod{p}$, i.e. $g^{pq-1} \equiv 1 \pmod p$. Hence $pq\equiv 1 \pmod {p-1}$, which reduces to $q\equiv 1\pmod {p-1}$. In particular $p-1\leq q-1$, i.e. $p\leq q$, contradiction.
allaith.sh
13.09.2024 02:26
$n$ is prime or $1$ Claim: $n$ is square-free. Proof: FTSOC assume that $p^2 | n$ such that $p$ is prime. let $x=p$ then $ p^n \equiv p \mod n \implies 0 \equiv p^n \equiv p \mod p^2$ contradiction. the remaining case is $n=pq$ such thar $p,q$ are primes: Let $g$ primitive root mod $p$ $h$ primitive root mod $q$ by CRT there is $x$ such that: $x \equiv g \mod p$ $x \equiv h \mod q$ then $x^{pq-1} \equiv 1 \mod pq$ $\implies p-1 | q-1 , q-1 | p-1 $ then $ p=q$ contradiction.