GCD of a prime number and and increasing number

Question

I saw from How to calculate "gcd product" $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ that for any prime number $n$, $$\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m) =n^{\lfloor m/n\rfloor}.$$

I can see that the product must be some sort of power of $n$.

But I don't see why it's true.

PS: I'm not a number theory expert and this is not for a number theory class.

Thanks.

Answer 1

Let $p$ be a prime. Given say $m > 0$, we are asked to calculate $\gcd(p, 1)\gcd(p, 2) \dots \gcd(p, m)$. Since $p$ is a prime and thus has only two divisors, for each factor $\gcd(p, k)$ there are only two cases:

• if $p$ does not divide $k$, then $\gcd(p, k) = 1$.
• if $p$ does divide $k$, then $\gcd(p, k) = p$.

With this observation, we see that $$\gcd(p, 1)\gcd(p, 2) \dots \gcd(p, m) = p^{\#\{k \in [m]: p\ \text{divides}\ k \}}. $$

It remains to show that $\#\{k \in [m]: p\ \text{divides}\ k \} = \lfloor m / p \rfloor$. In short, the left set is counting multiples of $p$ that are less than $m$. You should convince yourself that this floor counts the same thing.