Let $ n > 1$ be an integer, and $ n$ can divide $ 2^{\phi(n)} + 3^{\phi(n)} + \cdots + n^{\phi(n)},$ let $ p_{1},p_{2},\cdots,p_{k}$ be all distinct prime divisors of $ n$. Show that $ \frac {1}{p_{1}} + \frac {1}{p_{2}} + \cdots + \frac {1}{p_{k}} + \frac {1}{p_{1}p_{2}\cdots p_{k}}$ is an integer. ( where $ \phi(n)$ is defined as the number of positive integers $ \leq n$ that are relatively prime to $ n$.)
Problem
Source: Chinese TST
Tags: modular arithmetic, number theory, relatively prime, number theory proposed
05.04.2008 12:21
Let $ n=3$, then $ \phi (n)=2$ and $ 2^2+3^2=13=p_1$ (k=1), therefoe $ \frac{1}{p_1}+\frac{1}{p_1}=\frac{2}{13}$ is not integer.
05.04.2008 17:13
Hello,But there is a condition:$ n$ can divide $ 2^{\phi(n)} + 3^{\phi(n)} + \cdots + n^{\phi(n)},$.
05.04.2008 18:05
Here is solution . Let $ n = \prod _{i = 1}^r p_i^{a_i}$ We have property : 1.$ \varphi (p_i^{a_i})|\varphi (n)$ . 2. $ \varphi (n)\geq a_i,\forall i = 1...r$ Now consider problem : $ T = \sum_{k = 2}^n k^{\varphi (n)} \equiv (\sum_{{j = 1}_{\gcd {j,p}} = 1}^nj) - 1(mod p_i^{a_i})$ We has $ n - \frac {n}{p}$ j such that $ \gcd(j,p) = 1$ so $ T\equiv n - \frac {n}{p} - 1$ $ \Leftrightarrow \frac {n}{p} + 1 \equiv 0(\mod p^{a_i})$ It follow that $ a_i = 1,\forall i = 1,..,r$ and $ p_i|\frac {n}{p_i} + 1$ So $ \frac {1}{p_1} + ... + \frac {1}{p_1....p_r}$ is an integer.
12.06.2008 16:42
It is well-known that $ \phi(n)=n\left(1-\frac{1}{p_1}\right)\dots\left(1-\frac{1}{p_k}\right)$, hence for all $ 1\leq i\leq k$,we have that $ p_i-1|\phi(n)$. And there are exactly $ \left[\frac{n}{p_i}\right]$ numbers among $ 2,3\dots,n$,that are divisible by $ p_i$. Also if $ a$ is not divsible by $ p_i$,then $ a^{\phi(n)}\equiv 1$ mod $ p$.So $ S=2^{\phi(n)} + 3^{\phi(n)} + \cdots + n^{\phi(n)}\equiv n-1-\left[\frac{n}{p_i}\right]$. But as we know $ p_i|n$ and $ n|S$,hence $ p_i|n-1-\left[\frac{n}{p_i}\right]$,or $ \boxed{\left[\frac{n}{p_i}\right]\equiv -1}$ mod $ p_i$. From boxed relation we conclude that $ p_i^2\not{|} n$.But this means that $ n=p_1p_2\dots p_k$,and $ \prod_{j\neq i}p_j\equiv -1$ mod $ p_i$. Since $ (p_i,p_j)=1$ for all $ i\neq j$,it is enough to show that $ \prod_{j\neq i}p_j+\sum_{k\neq i}\left(\prod_{j\neq k}p_j\right)+1$ is divisible by $ p_i$, which is clearly true,because as we've observed $ \prod_{j\neq i}p_j\equiv -1$ mod $ p_i$
21.12.2009 23:18
Here is my solution; $ n = p_{1}^{\alpha_{1}}...p_{i}^{\alpha{i}}...p_{k}^{\alpha{k}}$ $ p_{i}|\sum_{j = 2}^{n} j^{\phi{n}}$ $ \implies$ $ \sum_{j = 2}^{n} j^{\phi{n}}\equiv n - 1 - p_{1}^{\alpha_{1}}.p_{i}^{\alpha_{i} - 1}...p_{k}^{\alpha{k}}$ if $ \alpha_{i}\geq 2$ $ \implies$ $ p_{i}|n - 1,p_{i}|n$ $ \implies$ $ p_{i}|1$ Contradiction! $ \implies$ $ p_{i}||n$ $ \implies$ $ n = p_{1}...p_{k}$ and $ \frac {n}{p_{i}}\equiv - 1\pmod{p_{i}}$ $ \implies$ $ (\sum_{i = 1}^{k} \frac {1}{p_{i}}) + \frac {1}{p_{1}..p_{k}}$ $ p_{i}|\frac {n}{p_{i}} + 1$ $ \implies$ $ (\sum_{i = 1}^{k} \frac {1}{p_{i}}) + \frac {1}{p_{1}..p_{k}}\in\mathbb{Z}$
29.04.2013 08:32
Suppose set of prime divisors of $n$ are $\{p_1,p_2,.....,p_k\}$.According to the given condition $p_i|n-1-\frac{n}{p_i}$ for all $1\leq i\leq k$.And so $p_i$ can divide $\frac{n}{p_i}$ for all $i$ and so $n$ must be a square free.So $p_i|1+\frac{n}{p_i}$ for all $i$ and now just multiplying those we're done.
31.07.2014 21:20
A bit too trivial for China TST. Note that \[\varphi (n) = \dfrac{n}{\displaystyle \prod_{i=1}^{k} p_i} (p_i-1) \equiv 0 \pmod{p_i-1} \quad \forall \ 1 \leq i \leq k.\] Hence, we have that $a^{\phi (n)} \equiv 1 \pmod{p}$ for all $p \mid n.$ Then, note that \begin{align*} \displaystyle \sum_{j=1}^{k} j^{\varphi (n)} & = \displaystyle \sum_{\substack{2 \leq j \leq k \\ \gcd (j, p) = 1}} j^{\varphi (n)} + \displaystyle \sum_{\substack{2 \leq j \leq k \\ p \mid j}} j^{\varphi (n)} \\ & \equiv \displaystyle \sum_{\substack{2 \leq j \leq k \\ \gcd (j, p) = 1}} j^{\varphi (n)} \pmod{p }\\ & \equiv n - 1 - \dfrac{n}{p} \equiv -\dfrac{n}{p}-1 \pmod{p}. \end{align*} Hence, we need $\dfrac{n}{p} + 1 \equiv 0 \pmod{p} \implies p \nmid \dfrac{n}{p}.$ Consequently, $v_p (n) \leq 1$ for all primes $p,$ so $n = p_1 p_2 \cdots p_k.$ Now, plugging $p_1, p_2, \cdots , p_k$ and multiplying these \[{n= p_1 p_2 \cdots p_k \mid \displaystyle \prod_{i=1}^{k} ( \dfrac{n}{p_i} + 1 ) \\ \implies p_1 p_2 \cdots p_k \mid \displaystyle \sum_{i=1}^{k} \displaystyle \prod_{\substack{1 \leq j \leq k \\ j \neq k}} p_i + 1 \ ^{(*)}\\ \implies \displaystyle \sum_{i=1}^{k} ( \displaystyle \prod_{\substack{1 \leq j \leq k \\ j \neq k}} p_i ) \cdot \dfrac{1}{p_1 p_2 \cdots p_k} = \displaystyle \sum_{i=1}^{k} p_i^{-1} + ( \displaystyle \prod_{i =1}^{k} p_i} )^{-1} \in \mathbb{Z}. \quad \blacksquare\] $^{(*)}$ This is because all other terms in the expansion of $\displaystyle \prod ( \dfrac{n}{p_i}+1 )$ are of the form $p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where the $a_i$'s are all positive integers.
13.09.2015 06:09
Indeed, too easy for China, Anyway noting that $\phi(p^{\alpha i}) \mid \phi(n)$ we conclude that $\frac{n}{p_i}+1\equiv 0 \bmod p^{\alpha_ i}$ which kills it.
23.08.2021 19:22
Since $\phi({p_i}^{\alpha_i})|\phi(N)$ for $N=\prod_{p_i}^{a_i}$ so $\frac{n}{p_i} \equiv -1 \pmod p_i$ So $p_i^2 \nmid n$ and hence $n = p_1 p_2 \cdots p_k$ and we are done since $ {n= p_1 p_2 \cdots p_k \mid \displaystyle \prod_{i=1}^{k} ( \dfrac{n}{p_i} + 1 ) \\ \implies p_1 p_2 \cdots p_k \mid \displaystyle \sum_{i=1}^{k} \displaystyle \prod_{\substack{1 \leq j \leq k \\ j \neq k}} p_i + 1 \ \\ \implies \displaystyle \sum_{i=1}^{k} ( \displaystyle \prod_{\substack{1 \leq j \leq k \\ j \neq k}} p_i ) \cdot \dfrac{1}{p_1 p_2 \cdots p_k} = \displaystyle \sum_{i=1}^{k} p_i^{-1} + ( \displaystyle \prod_{i =1}^{k} p_i} )^{-1} \in \mathbb{Z}. \quad $
14.04.2023 01:31
This is just an easy grind. Note that for each $p_i$ and $a$, either $p_i \mid a^{\phi(n)}$ or $p_i - 1 \mid a^{\phi(n)}$. Thus, the sum in the expression is congruent to the number of $a$ which are not multiples of $p_i$, which is equal to $n-1-\frac n{p_i}$ modulo $p_i$. Thus $p_i \mid \frac n{p_i} + 1$, which implies that $n$ is squarefree, and also $$p_1p_2\cdots p_k \mid \sum_{i=1}^k \frac n{p_i} + 1,$$which implies the desired.
24.10.2024 18:23
It suffices to show that for each prime $p_i|n,$ we have that $p_i | \prod_{1 \leq j \leq k, j \neq i} p_j + 1.$ By the condition, it follows that $\sum_{j=2}^{n} j^{\phi(n)} \equiv 0 \pmod{p_i}.$ Clearly for $j$ relatively prime to $p_i,$ $j^{\phi(n)} \equiv 1,$ while otherwise we get zero. Therefore, we have that $$n-1-\frac{n}{p_i} \equiv 0 \pmod{p_i}.$$If $p_i | \frac{n}{p_i},$ this yields $-1 \equiv 0,$ which is absurd. Therefore, $n$ is squarefree for all $p_i$ so $n=p_1p_2 \cdots p_k,$ and substituting yields the desired result. QED
01.11.2024 03:32
Claim: For any prime $p \mid n$, we have $n \equiv -p \pmod{p^2}$. Proof: Fix some prime $p\mid n$. Note that $p - 1 \mid \phi(n)$, so $2^{\phi(n) } + 3^{\phi(n)} + \cdots + n^{\phi(n)}$ in modulo $p$ is just the number of positive integers in $[2,n]$ not divisible by $p$, which is $n - \frac np - 1$. This must be divisible by $p$, so $p\mid \frac np + 1 $, so $\frac np \equiv -1 \pmod p$. If we let $\frac np = pk - 1$, we have $n = p^2 k - p$, as desired. $\square$ This for one implies that $n$ is squarefree, so $n = p_1 p_2 \cdots p_k$. Now let $S$ be \[ \frac {1}{p_{1}} + \frac {1}{p_{2}} + \cdots + \frac {1}{p_{k}} + \frac {1}{p_{1}p_{2}\cdots p_{k}}\] Suppose it wasn't an integer. Let $p$ be a prime so that $\nu_p(S) < 0$. This obviously means $p \in \{p_1, p_2, \ldots, p_k\}$. WLOG $p = p_1$. Then note that $\nu_p \left( S - \frac{1}{p_1} - \frac{1}{p_1 \cdot p_2 \cdots p_k} \right) = \nu_p \left( \frac{1}{p_2} + \frac{1}{p_3} + \cdots + \frac{1}{p_k} \right) = 0$. Thus it suffices to show that $\nu_p \left( \frac{1}{p_1} + \frac{1}{p_1 \cdot p_2 \cdots p_k} \right) \ge 0$, which is equivalent to \[ \nu_p \left( \frac{1}{p} + \frac 1n \right) \ge 0\] Note that $\frac 1p + \frac 1n = \frac{p + n}{p^2}$. Since $p^2 \mid p + n$, $\nu_p(p + n) \ge 2$, so \[\nu_p \left( \frac 1p + \frac 1n \right) = \nu_p(p + n) - \nu_p(p^2) \ge 0,\]as desired.