I want to show that f(n)=gcd(a,n)f(n) = \gcd(a,n) where a is any natural number, is a multiplicative function.

I know I need to show that f(mn)=f(n)∗f(m)f(mn)=f(n)*f(m), but I do not know how to do this.

=================

=================

1 Answer

1

=================

If you prove that

gcd(a,x)=∏p∣apmin(νp(a),νp(x)) \gcd(a,x) = \prod_{p\mid a} p^{\min(\nu_p(a),\nu_p(x))}

where νp(x)=max{m∈N:pm∣x}\nu_p(x)=\max\{m\in\mathbb{N}: p^m\mid x\} the question becomes trivial. If xx and yy are coprime integers they have no common prime factor, so

gcd(a,xy)=∏p∣apmin(νp(a),νp(xy))=∏p∣x∧p|apmin(νp(a),νp(xy))∏p∣y∧p|apmin(νp(a),νp(xy)) \gcd(a,xy) = \prod_{p\mid a}p^{\min(\nu_p(a),\nu_p(xy))}=\prod_{p\mid x\,\wedge\, p|a}p^{\min(\nu_p(a),\nu_p(xy))}\prod_{p\mid y\,\wedge\, p|a}p^{\min(\nu_p(a),\nu_p(xy))}

and the RHS equals

∏p∣x∧p|apmin(νp(a),νp(x))∏p∣y∧p|apmin(νp(a),νp(y))=gcd(a,x)gcd(a,y). \prod_{p\mid x\,\wedge\, p|a}p^{\min(\nu_p(a),\nu_p(x))}\prod_{p\mid y\,\wedge\, p|a}p^{\min(\nu_p(a),\nu_p(y))}=\gcd(a,x)\gcd(a,y).