Integer

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Integer

G H J

Reveal topic tags

modular arithmetic

relatively prime

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Chinese TST

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

237 posts

#1 h Apr 5, 2008, 9:14 AM • 2 Y

Y by Adventure10, Mango247

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$ .)

This post has been edited 4 times. Last edited by Fang-jh, Apr 5, 2008, 10:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#2 h Apr 5, 2008, 9:21 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2382 posts

#3 h Apr 5, 2008, 2:13 PM • 3 Y

Y by Adventure10, Derpy_Creeper, Mango247

Hello,But there is a condition: $n$ can divide $2^{\phi(n)} + 3^{\phi(n)} + \cdots + n^{\phi(n)},$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#4 h Apr 5, 2008, 3:05 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1363 posts

Erken

#5 h Jun 12, 2008, 1:42 PM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

394 posts

cnyd

#6 h Dec 21, 2009, 9:18 PM • 1 Y

Y by Adventure10

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1479 posts

#7 h Apr 29, 2013, 5:32 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

339 posts

#8 h Jul 31, 2014, 6:20 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#9 h Sep 13, 2015, 3:09 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#10 h Aug 23, 2021, 4:22 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8859 posts

#11 h Apr 13, 2023, 10:31 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

575 posts

#12 h Oct 24, 2024, 3:23 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5604 posts

#13 h Nov 1, 2024, 12:32 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

391 posts

alexanderhamilton124

#14 h Apr 9, 2025, 1:33 PM • 1 Y

Y by L13832

To prove 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, we can show that
$v_{p_i}\left(\frac{1}{p_1} + \frac{1}{p_2} + \cdots + \frac{1}{p_k} + \frac{1}{p_1 p_2 \cdots p_k}\right) \geq 0$ for all $1 \leq i \leq k$ .

Note that
$1^{\phi(n)} + \cdots + n^{\phi(n)} = \frac{n}{p_i}(p_i - 1) \pmod{p_i} \implies -1 \equiv \frac{n}{p_i}(p_i - 1)$ since
$2^{\phi(n)} + \cdots + n^{\phi(n)} \equiv 0 \pmod{p_i}.$ This also means $n$ is squarefree, and
$\frac{n}{p_i} \equiv -1 \pmod{p}.$
Note that
$v_{p_i}\left(\frac{1}{p_1} + \frac{1}{p_2} + \cdots + \frac{1}{p_k} + \frac{1}{p_1 p_2 \cdots p_k}\right) = v_{p_i}\left(\left(\frac{1}{p_i} + \frac{1}{p_1 \cdots p_k}\right) + \frac{1}{p_2} + \cdots\right).$
Note that
$v_{p_i}\left(\frac{1}{p_2} + \cdots\right) \geq 0$ since no denominator is divisible by $p_i$ . Meanwhile,
$\frac{1}{p_i} + \frac{1}{p_1 \cdots p_k} = \frac{1}{p_i} + \frac{1}{n}, \quad \text{since } n \text{ is squarefree,}$ which is equal to
$\frac{1}{p_i} \left(1 + \frac{p_i}{n}\right).$ Note that
$\frac{p_i}{n} \equiv -1 \pmod{p_i},$ so
$p_i \mid \left(1 + \frac{p_i}{n}\right),$ hence
$v_{p_i}\left(\frac{1}{p_i} + \frac{1}{p_1 \cdots p_k}\right) \geq 0,$ which means the $v_{p_i}$ of the overall sum must be greater than or equal to 0 as well, so we're done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a