For each $n\in \mathbb{N}$, let $S(n)$ be the sum of all numbers in the set $\{ 1, 2, 3, \cdots , n \}$ which are relatively prime to $n$. $(a)$ Show that $2 \cdot S(n)$ is not a perfect square for any $n$. $(b)$ Given positive integers $m, n$, with odd $n$, show that the equation $2 \cdot S(x) = y^n$ has at least one solution $(x, y)$ among positive integers such that $m|x$.
Problem
Source:
Tags: number theory, relatively prime, number theory unsolved
ehsan2004
09.12.2010 16:01
Hint: $S(n)=\frac12 n \varphi (n)$.
kmh1
21.01.2012 18:49
(1)Let $ n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k} $.($ p_1<p_2<...<p_k $ are different primes.) Obviously, $ 2S(n)=n\phi(n)=p_1^{2\alpha_1-1}p_2^{2\alpha_2-1}...p_k^{2\alpha_k-1} $. Since $ p_k $ is bigger than all of $ p_1-1, p_2-1,...,p_k-1 $, $ p_k $ does not divide $ (p_1-1)(p_2-1)...(p_k-1) $. Therefore, $ p_k^{2\alpha_k-1}\parallel2S(n) $. Thus $ 2S(n) $ is not a perfect square. (2)Let $ m=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k} $.($ p_1<p_2<...<p_k $) Let $ max\alpha_1,\alpha_2,...,\alpha_k=b $. Also, let all primes not greater than $ p_k $ be $ q_1,q_2,...,q_k $. Let $ x=q_1^{b+\beta_1}q_2^{b+\beta_2}...q_k^{b+\beta_k} $. Then $ m\mid $ $ x $. We will select $ \beta_i $ later. We know that $ 2S(x)=x\phi(x)=q_1^{2b+2\beta_1-1}q_2^{2b+2\beta_2-1}...q_k^{2b+2\beta_k-1}(q_1-1)(q_2-1)...(q_k-1) $. Let $ (q_1-1)(q_2-1)...(q_k-1)=q_1^{\gamma_1}q_2^{\gamma_2}...q_k^{\gamma_k} $. Then $ 2S(x)=q_1^{2b+\gamma_1-1+2\beta_1}q_2^{2b+\gamma_2-1+2\beta_2}...q_k^{2b+\gamma_k-1+2\beta_k} $. $ n $ is odd, so there exists $ \beta_i $ such that $ 2\beta_i\equiv1-\gamma_i-2b(modn) $. Then all the prime powers of $ 2S(x) $ are multiples of n, so there exists $ y $ such that $ 2S(x)=y^n $. Then $ x,y $ satisfy the conditions.
Mosquitall
24.01.2012 19:35
ehsan2004 wrote: Hint: $S(n)=\frac12 n \varphi (n)$. Good hint , i have solution with using your hint