Prove that gcd(n;n+k)=gcd(n;k) ?

The greatest common divisor function, #gcd(a,b)#, returns the largest number #n# such that #n# is a factor of both #a# and #b#.

Factorize #a# and #b#:

• #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 #p_0,p_1,p_2,ldots# are the prime numbers #2,3,5,ldots#

Then, #gcd(a,b)=p_0^(min(a_0,b_0))p_1^(min(a_1,b_1))p_2^(min(a_2,b_2))ldots#

With this, we can proceed to prove that #gcd(n,k)=gcd(n,n+k)#.

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:
#n+k=p_0^(min(n_0,k_0))p_1^(min(n_1,k_1))p_2^(min(n_2,k_2))ldots(p_0^(n_0-min(n_0,k_0))p_1^(n_1-min(n_1,k_1))p_2^(n_2-min(n_2,k_2))ldots+p_0^(k_0-min(n_0,k_0))p_1^(k_1-min(n_1,k_1))p_2^(k_2-min(n_2,k_2))ldots)#

Define #c=p_0^(n_0-min(n_0,k_0))p_1^(n_1-min(n_1,k_1))p_2^(n_2-min(n_2,k_2))ldots+p_0^(k_0-min(n_0,k_0))p_1^(k_1-min(n_1,k_1))p_2^(k_2-min(n_2,k_2))ldots# and notice that the part factorized out is exactly equal to #gcd(n,k)#. Therefore, we have
#n+k=cgcd(n,k)#.

Realize now that the #c=p_0^(n_0-min(n_0,k_0))p_1^(n_1-min(n_1,k_1))p_2^(n_2-min(n_2,k_2))ldots+p_0^(k_0-min(n_0,k_0))p_1^(k_1-min(n_1,k_1))p_2^(k_2-min(n_2,k_2))ldots# is not divisible by any of the prime factors #p_0,p_1,p_2,ldots# of #n# and #k#. This is because #c# is the sum of two terms, and exactly one of the terms is divisible by each of #p_0,p_1,p_2,ldots#

Thus, #c# does not share any prime factors with #n=p_0^(n_0)p_1^(n_1)p_2^(n_2)ldots# and #k=p_0^(k_0)p_1^(k_1)p_2^(k_2)ldots#.

So, since #gcd(n,k)# is the shared factor among #n#,#k#, and #n+k#, and there is no shared factors among #c=(n+k)/gcd(n,k)#, #n#, and #k#, the greatest shared common factor between #n+k# and either #n# or #k# must be #gcd(n,k)#.

Therefore, #gcd(n,k)=gcd(n,n+k)=gcd(k,n+k)#.

The greatest common divisor function, #gcd(a,b)#, returns the largest number #n# such that #n# is a factor of both #a# and #b#.

With this, we can proceed to prove that #gcd(n,k)=gcd(n,n+k)#.

Define #c=gcd(n,k)#. Then, #c|n# and #c|k#, where the notation #a|b# signifies that #b# is divisible by #a#. Then, it is obvious that #c|n+k#.

(For proof, #c|n# and #c|k# implies that #n=ac# and #k=bc#, where #a# and #b# are integers. Then, #n+k=ac+bc=c(a+b)#, which means that #c|n+k#.)

So, we have shown that #c=gcd(n,k)# is a factor of #n#, #k#, and #n+k#. We now need to prove that #c# is the largest common factor of #n# and #n+k#.

Suppose that there is a larger common factor between #n# and #n+k# called #d#. In other words, there exists a #d>c# such that #d|n# and #d|n+k#. But this implies that there exists integers #a# and #b# such that #n=ad# and #n+k=bd#, or #k=bd-n=bd-ad=d(b-a)#, or #k|d#.

But this is impossible since this entails that #d# is a common factor between #n# and #k#. Yet, #c#, which is defined as the greatest common divisor of #n# and #k# is smaller than #d#. Thus, the original assertion that there is a larger common factor between #n# and #n+k# called #d# such that #d>c# is false.

Then, we have proven that #c=gcd(n,k)# is a factor of both #n# and #n+k# and that there is no factor of #n# and #n+k# that is greater than #c#. By definition, #c# is then the greatest common divisor of #n# and #n+k#. Thus, #c=gcd(n,k)=gcd(n,n+k)#.

#"Q.E.D."#

Recall the Definition of GCD :

#"The "gcd(a;b)=c iff (g1): c |a, c|b; (g2): d|a, d|b rArr d|c#.

Suppose that, #gcd(n;k)=c and gcd(n;n+k)=c'#.

To prove that, #c=c'#.

#gcd(n;k)=c :. c|n and c|k. :. c|(n+k)#.

Thus, #c|n, c|(n+k)#.

Since, #gcd(n;n+k)=c' :.(g2)rArrc|c'............(ast^1)#.

Conversely, #gcd(n;n+k)=c' :. c'|n and c'|(n+k)#.

#:. c'|{(n+k)-n}, i.e., c'|k#. Thus, #c'|n, and c'|k#.

Then, since, #gcd(n;k)=c," by "(g2), c'|c.............(ast^2)#.

#"By "(ast^1) and (ast^2), c=c'#.

Enjoy Maths., and Spread the Joy!