3
$\begingroup$

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor?

Can this be solved using Euler Totient function?

My Approach:-

For any prime number $n$, $\operatorname{gcdp}(n,m)=n^{\operatorname{floor}(m/n)}$.

Is there any way to solve it for any non-prime $n$?

$\endgroup$
4
$\begingroup$

Let $$f_m(n)=\gcd(n,1)\gcd(n,2)\gcd(n,3)\cdots \gcd(n,m).$$ To extend your computation of $f_m(n)$ beyond the primes, note that fox fixed $n$ the function $f_m$ is multiplicative: If $\gcd(a,b)=1$, then $f_m(ab)=f_m(a)f_m(b)$.

Thus it is enough to know $f$ at prime powers. In particular, since you know $f_m(p)$ for prime $p$, you know $f_m(n)$ for all square-free $n$.

Now let us get a handle on $f_m(p^2)$, where $p$ is prime. We will pick up a $p$ for every number $i\le m$ such that $i$ is divisible by $p$. We will pick up an extra $p$ for every number $i\le m$ which is divisible by $p^2$. Thus the total number of $p$'s that we pick up is $\left\lfloor\frac{m}{p}\right\rfloor+\left\lfloor\frac{m}{p^2}\right\rfloor$. That gives us the exponent of $p$ in $f_m(p^2)$.

Exactly the same reasoning can be used to find the exponent of $p$ in $f_m(p^3)$. We get $\left\lfloor\frac{m}{p}\right\rfloor+\left\lfloor\frac{m}{p^2}\right\rfloor+ \left\lfloor\frac{m}{p^3}\right\rfloor$. The idea readily generalizes to $f_m(p^k)$.

Thus we can get an explicit expression for $f_m(n)$, once we know the prime power factorization of $n$.

$\endgroup$

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.