# Thread: Prove the following sum

1. ## 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....

2. ## Re: Prove the following sum Originally Posted by gaussrelatz 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.

3. ## 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?

4. ## Re: Prove the following sum Originally Posted by gaussrelatz 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.

5. ## Re: Prove the following sum

So basically my proof of the problem is correct all around?

6. ## Re: Prove the following sum

I believe so. It looks correct to me.

7. ## Re: Prove the following sum

Ok thank you for the confirmation.