Prove that gcd(n;n+k)=gcd(n;k) ?
please help me i cant do this
please help me i cant do this
3 Answers
The greatest common divisor function,
Factorize
#a=p_0^(a_0)p_1^(a_1)p_2^(a_2)ldots# #b=p_0^(b_0)p_1^(b_1)p_2^(b_2)ldots#
where
Then,
With this, we can proceed to prove that
First, we have
#n=p_0^(n_0)p_1^(n_1)p_2^(n_2)ldots# #k=p_0^(k_0)p_1^(k_1)p_2^(k_2)ldots# #n+k=p_0^(n_0)p_1^(n_1)p_2^(n_2)ldots+p_0^(k_0)p_1^(k_1)p_2^(k_2)ldots#
Before moving on, let us try to factorize this slightly:
Define
Realize now that the
Thus,
So, since
Therefore,
The greatest common divisor function,
With this, we can proceed to prove that
Define
(For proof,
So, we have shown that
Suppose that there is a larger common factor between
But this is impossible since this entails that
Then, we have proven that
Kindly refer to a Proof given in the Explanation.
Explanation:
Recall the Definition of GCD :
Suppose that,
To prove that,
Thus,
Since,
Conversely,
Then, since,
Enjoy Maths., and Spread the Joy!