Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Prove the following sum

  1. #1
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    45

    Prove the following sum

    So there is the problem in arithmetic functions chapter and the problem goes:


    Prove for all positive integers $n$:


    $$\sum_{a=1,(a,n)=1}^n (a-1,n)=d(n)\phi(n)$$


    So here is my solution, could anyone tell me if my solution is correct, or wrong?


    $proof:$ if we denote $\sum_{a=1,(a,n)=1}^n (a-1,n)=\sigma(n)$, we consider the case when $n=p^r$, where $r\in \mathbb{N}$, as for $r=0$ it clearly holds.
    $$\sigma(p^r)=\sum_{a=1,(a,p^r)=1}^{p^r} (a-1,p^r)$$
    $$=\sum_{j=0}^{p^{r-1}-1}\sum_{i=1}^{p-1} (i+jp-1,p^r)$$
    $$=\sum_{j=0}^{p^{r-1}-1} (p-2+p(j,p^{r-1}))$$
    $$=(p-2)p^{r-1}+p[1(p^{r-1}-p^{r-2})+p(p^{r-2}-p^{r-3})+...+ p^{r-2}(p-1)+p^{r-1}]$$
    $$=p^r-2p^{r-1}+rp^r-p^{r-1}(r-1)$$
    $$=(r+1)(p^r-p^{r-1})$$
    $$=d(p^r)\phi(p^r)$$

    Does this work? Because it seems quite consistent to me, I am just double checking as I have to submit this problem next week....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,387
    Thanks
    1345

    Re: Prove the following sum

    Quote Originally Posted by gaussrelatz View Post
    So there is the problem in arithmetic functions chapter and the problem goes:


    Prove for all positive integers $n$:


    $$\sum_{a=1,(a,n)=1}^n (a-1,n)=d(n)\phi(n)$$


    So here is my solution, could anyone tell me if my solution is correct, or wrong?


    $proof:$ if we denote $\sum_{a=1,(a,n)=1}^n (a-1,n)=\sigma(n)$, we consider the case when $n=p^r$, where $r\in \mathbb{N}$, as for $r=0$ it clearly holds.
    $$\sigma(p^r)=\sum_{a=1,(a,p^r)=1}^{p^r} (a-1,p^r)$$
    $$=\sum_{j=0}^{p^{r-1}-1}\sum_{i=1}^{p-1} (i+jp-1,p^r)$$
    $$=\sum_{j=0}^{p^{r-1}-1} (p-2+p(j,p^{r-1}))$$
    $$=(p-2)p^{r-1}+p[1(p^{r-1}-p^{r-2})+p(p^{r-2}-p^{r-3})+...+ p^{r-2}(p-1)+p^{r-1}]$$
    $$=p^r-2p^{r-1}+rp^r-p^{r-1}(r-1)$$
    $$=(r+1)(p^r-p^{r-1})$$
    $$=d(p^r)\phi(p^r)$$

    Does this work? Because it seems quite consistent to me, I am just double checking as I have to submit this problem next week....
    You still need to show that $\displaystyle \sigma(p^rq^s) = \sigma(p^r)\sigma(q^s)$ (which should be fairly trivial, given what you have already done), but otherwise, it looks correct.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    45

    Re: Prove the following sum

    For that part, I used Chinese remainder theorem to show that $\displaystyle \sigma (m_1 m_2)=\sigma(m_1) \sigma(m_2)$, where the proof I wrote goes like:

    proof:
    $$\sigma (m_1 m_2)=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2}(a-1,m_1m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2}(a-1,m_1)(a-1,m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a \in A, b \in B}(\alpha-1,m_1)(\beta-1,m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a \in A}(\alpha-1,m_1)\sum_{ b \in B}(\beta-1,m_2)$$
    $$\sigma (m_1 m_2)=\sigma (m_1)\sigma (m_2)$$

    Further remarks, if we let $\displaystyle A $ be the set of all positive integers less than or equal to $\displaystyle m_1$ , which are relatively prime to $\displaystyle m_1 $, and $\displaystyle B $ similar to $\displaystyle A$ with $\displaystyle m_2$, then $\displaystyle A$ and $\displaystyle B$ are complete reduced residue systems modulo $\displaystyle m_1$ and$\displaystyle m_2$. Then by the Chinese remainder theorem we have for $\displaystyle 1 \le a \le m_1m_2$, and $\displaystyle (a, m_1m_2)=1$, this implies that there exists some $\displaystyle !$ ordered pairs of $\displaystyle (a,b) \in A \times B$ such that $\displaystyle a = \alpha \bmod m_1$ and $\displaystyle a=\beta \bmod m_2 $, hence the above follows.

    Does this reasoning make sense?
    Last edited by gaussrelatz; Nov 17th 2017 at 07:56 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,387
    Thanks
    1345

    Re: Prove the following sum

    Quote Originally Posted by gaussrelatz View Post
    For that part, I used Chinese remainder theorem to show that $\displaystyle \sigma (m_1 m_2)=\sigma(m_1) \sigma(m_2)$, where the proof I wrote goes like:

    proof:
    $$\sigma (m_1 m_2)=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2}(a-1,m_1m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2}(a-1,m_1)(a-1,m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a \in A, b \in B}(\alpha-1,m_1)(\beta-1,m_2)$$
    $$\sigma (m_1 m_2)=\sum_{a \in A}(\alpha-1,m_1)\sum_{ b \in B}(\beta-1,m_2)$$
    $$\sigma (m_1 m_2)=\sigma (m_1)\sigma (m_2)$$

    Further remarks, if we let $\displaystyle A $ be the set of all positive integers less than or equal to $\displaystyle m_1$ , which are relatively prime to $\displaystyle m_1 $, and $\displaystyle B $ similar to $\displaystyle A$ with $\displaystyle m_2$, then $\displaystyle A$ and $\displaystyle B$ are complete reduced residue systems modulo $\displaystyle m_1$ and$\displaystyle m_2$. Then by the Chinese remainder theorem we have for $\displaystyle 1 \le a \le m_1m_2$, and $\displaystyle (a, m_1m_2)=1$, this implies that there exists some $\displaystyle !$ ordered pairs of $\displaystyle (a,b) \in A \times B$ such that $\displaystyle a = \alpha \bmod m_1$ and $\displaystyle a=\beta \bmod m_2 $, hence the above follows.

    Does this reasoning make sense?
    Upon a quick review, it looks ok to me.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    45

    Re: Prove the following sum

    So basically my proof of the problem is correct all around?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,387
    Thanks
    1345

    Re: Prove the following sum

    I believe so. It looks correct to me.
    Thanks from gaussrelatz
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    45

    Re: Prove the following sum

    Ok thank you for the confirmation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Sep 16th 2017, 02:22 AM
  2. X~ Ber(x,p) prove μx=p
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: Oct 22nd 2010, 11:23 PM
  3. Prove
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: Jan 11th 2010, 02:56 PM
  4. Replies: 2
    Last Post: Aug 28th 2009, 02:59 AM
  5. Prove
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Oct 22nd 2008, 03:28 PM

/mathhelpforum @mathhelpforum