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

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.


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


$\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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.