Maths Olympiad Prep

Library / /370 of 520

Number theory Difficulty 6.4 National olympiad Prove it

Lemma 7 Let a,ba, b be two positive integers and (a,b)=1(a, b)=1, then we have d(ab)=d(a)d(b)d(a b)=d(a) d(b).

Solution

Let a=p1a1pnan,b=q1β1qmβma=p_{1}^{a_{1}} \cdots p_{n}^{a_{n}}, \quad b=q_{1}^{\beta_{1}} \cdots q_{m}^{\beta_{m}}, where p1,,pn,q1,,qmp_{1}, \cdots, p_{n}, q_{1}, \cdots, q_{m} are all prime numbers and α1,,αn,β1,,βm\alpha_{1}, \cdots, \alpha_{n}, \beta_{1}, \cdots, \beta_{m} are all positive integers. Since (a,b)=1(a, b)=1, we know that any pi(i=1,,n)p_{i}(i=1, \cdots, n) and any qi(j=1,,m)q_{i}(j=1, \cdots, m) cannot be equal. Therefore, by Lemma 6, we have
d(ab)=d(p1α1pnαnq1β1qmβm)=(α1+1)(αn+1)(β1+1)(βm+1)\begin{aligned} d(a b) & =d\left(p_{1}^{\alpha_{1}} \cdots p_{n}^{\alpha_{n}} q_{1}^{\beta_{1}} \cdots q_{m}^{\beta_{m}}\right) \\ & =\left(\alpha_{1}+1\right) \cdots\left(\alpha_{n}+1\right)\left(\beta_{1}+1\right) \cdots\left(\beta_{m}+1\right) \end{aligned}

Again, by Lemma 6, we have
d(a)d(b)=d(p1a1pnαn)d(q1β1qmβm)=(α1+1)(αn+1)(β1+1)(βm+1)\begin{array}{l} d(a) d(b)=d\left(p_{1}^{a_{1}} \cdots p_{n}^{\alpha_{n}}\right) d\left(q_{1}^{\beta_{1}} \cdots q_{m}^{\beta_{m}}\right) \\ \quad=\left(\alpha_{1}+1\right) \cdots\left(\alpha_{n}+1\right)\left(\beta_{1}+1\right) \cdots\left(\beta_{m}+1\right) \end{array}

From (46) and (47), Lemma 7 is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.