Question

Need a proof

Answer 1

\[Prove that \phi(m_1)+\phi(m_2)+...+\phi(m_n)=\gcd(m,n)\]

Answer 2

where m1,m2,...,mn divides both m and n

Answer 3

@ganeshie8

Answer 4

@Kainui

Answer 5

m1, m2,...,mn are positive as well

Answer 6

Hey!

Answer 7

What do u need help in

Answer 8

Your statement in compact form :
\[\large a = \sum\limits_{d\mid a} \phi(d)\]

Proof :
Consider a partition of integers, \(\{1,2,3,\ldots,a\}\) :
\[S_d=\{b : \gcd(a,b)=d; 1\le b\le a\}\]
Notice that \(\gcd(a,b)=d\iff \gcd(a/d,b/d)=1\). That means \(|S_d| = \phi(a/d)\).
Therefore, \[\large a = \sum\limits_{d\mid a} \phi(a/d) = \sum\limits_{d\mid a} \phi(d) \]

Answer 9

Thanks @ganeshie8 .:)

Answer 10

I dont have number theory but I needed a proof to be sure my claim in true, the result I will use in another problem.

Answer 11

np :)
that notation isn't hard to understand, let me know if you want the detailed proof

Answer 12

You already gave me in my inbox. And I understood, its nice and easy. Thanks to Gauss.:)

Answer 13

hi
@ganeshie8

Answer 14

Heyy

Answer 15

I read the proof of Gauss.

Answer 16

But I dont know how to prove what is given in the question