Question

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

please help me i cant do this

Answer 1

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)`.

Answer 2

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."`

Answer 3

Kindly refer to a Proof given in the Explanation.

Explanation:

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!