# greatest common divisor properties

Let $f(N,x)$ is $N$ repeated $x$ times. So $f(123,2)=123123$ and
$f(123,3)=123123123$

In the problem we are given $a$ and $b$ and $N$ and we need to calculate $\gcd(f(N,a),f(N,b))$.

How do we prove that $\gcd(f(N,a),f(N,b))=f(N,\gcd(a,b))$?

It has been proved that $\gcd(f(N,a),f(N,b))=\gcd(f(N,a-b),f(N,b))$.

Well, the 2nd one gives you the solution, I think.

$\gcd(f(N,a),f(N,b))=\gcd(f(N,a-b),f(N,b))$

If you continue writing/applying it (i.e. if you keep descending), you will end up with $\gcd(f(N,d),f(N,d))$ where this $d$ is the $\gcd(a,b)$. So this 2nd equation basically repeats the algorithm for finding the $\gcd(a,b)$.

Example:

$\gcd(f(N,24),f(N,44))=\gcd(f(N,20),f(N,24))=\gcd(f(N,4),f(N,20))=\gcd(f(N,4),f(N,16))=\gcd(f(N,4),f(N,12))=\gcd(f(N,4),f(N,8))=\gcd(f(N,4),f(N,4)) = f(N,4) = f(N,gcd(24,44))$

It's not a surprise that $4=gcd(24,44)$.

• can u justify your claim with an example – satyajeet jha Apr 8 '16 at 21:52
• @satya Sure, done. You can try another couple of numbers (other than 24,44). – peter.petrov Apr 8 '16 at 21:56
• @peter.potrov yes it works fine – satyajeet jha Apr 8 '16 at 22:08