Let $n = p_1p_2 \dots p_k$ be the product of distinct primes $p_1, p_2, \dots , p_k$, with $k > 1$. Find all $n$ such that $n$ is multiple of $p_1 - 1, p_2 - 1, \dots , p_k - 1$.
Problem
Source: Brazil Cono Sur TST 2023 - T1/P1
Tags: number theory
19.01.2025 08:55
Let $S$ be set of prime $p$ such that $p-1$ is square free and every divisor $d$ of $p-1$ belong to $S \cup \{1 \}$ Consider the smallest prime $p \mid n$ not belong to $S$. This mean either $p-1$ is non square free which contradict the fact that $n$ is square free or some prime divisor $k$ of $p-1$ isn't belong to $S$, which also contradict, since $k \mid p-1 \mid n$ but $p$ is the smallest prime that doesn't belong to $S$. So, all prime divisor of $n$ belong to $S$. Now, one can easily check that $2,3,7,43 \in S$. Suppose there exist prime $p \neq 2,3,7,43 \in S$ Consider smallest such $p$, we get that $$\frac{p-1}{43} \in \{2,6,42,\} \rightarrow p \in \{87, 247, 807\}$$None of these are prime number. So $S = \{2,3,7,43\}$ By simply checking the remaining $16$ number, we get that $n = 2,6,42,1806 \blacksquare$
19.01.2025 14:51
As we have : $n=p_1p_2\ldots p_k$ we may consider WLOG that $p_1<p_2<\ldots <p_k$. Having that : $p_1-1;p_2-1;\ldots ;p_k-1$ are divisors of $n$, hence we get $2\mid n$ meaning $p_1=2$. So we have $p_2-1\mid n$, consider $r$ a prime factor of $p-2-1$ so we get : $r<p_2$ meaning that $r=2$ to not contradict the minimality of $p_2$ we get $r=2$ meaning $p_2-1=2^k\mid n$ hence $p_2=2+1=3.$ Doing the same thing to $p_3$ we get $p_3-1=2^x3^y\mid n$ hence : $p_3-1=2$ or $p_3-1=3$ or $p_3-1=6$, hence $p_3=7$. Doing the same thing over again for $p_4$ we get : $p_4-1=2^x3^y7^z\mid n$ hence : $p_4=43.$ We cannot continue to $p_5$ as we wont get prime factors any more. So $n\in\{2;6;42;1806\}$
20.01.2025 18:11
This problem is a subproblem of https://artofproblemsolving.com/community/c1123852h2136459p15658099.