Maths Olympiad Prep

Library / /434 of 520

Number theory Difficulty 6.8 National olympiad Prove it

Property VIII δm(ab)=δm(a)δm(b)\delta_{m}(a b)=\delta_{m}(a) \delta_{m}(b) holds if and only if
(δm(a),δm(b))=1\left(\delta_{m}(a), \delta_{m}(b)\right)=1

Solution

Let δ=δm(a),δ=δm(b),δ=δm(ab),η=[δm(a),δm(b)]\delta^{\prime}=\delta_{m}(a), \delta^{\prime \prime}=\delta_{m}(b), \delta=\delta_{m}(a b), \eta=\left[\delta_{m}(a), \delta_{m}(b)\right].
Sufficiency We have

So δδδ\delta^{\prime} \mid \delta \delta^{\prime \prime}. From this and (δ,δ)=1\left(\delta^{\prime}, \delta^{\prime \prime}\right)=1, it follows that δδ\delta^{\prime} \mid \delta. Similarly, we have
1(ab)8(ab)8δb8δ(modm)1 \equiv(a b)^{8} \equiv(a b)^{8 \delta^{\prime}} \equiv b^{8 \delta^{\prime}}(\bmod m)

So δδδ\delta^{\prime \prime} \mid \delta \delta^{\prime}. From this and (δ,δ)=1\left(\delta^{\prime}, \delta^{\prime \prime}\right)=1, it follows that δδ\delta^{\prime \prime} \mid \delta, and thus from δδ,δδ\delta^{\prime}\left|\delta, \delta^{\prime \prime}\right| \delta and (δ,δ)=1\left(\delta^{\prime}, \delta^{\prime \prime}\right)=1, it follows that δδδ\delta^{\prime} \delta^{\prime \prime} \mid \delta. Additionally, it is clear that
(ab)γγ1(modm),(a b)^{\gamma^{\gamma}} \equiv 1(\bmod m),

So, δδδ\delta \mid \delta^{\prime} \delta^{\prime \prime}. Therefore, δ=δδ\delta=\delta^{\prime} \delta^{\prime \prime}.
Necessity We have
(ab)η1(modm)(a b)^{\eta} \equiv 1(\bmod m)

So δη\delta \mid \eta. On the other hand, it is clear that ηδδ\eta \mid \delta^{\prime} \delta^{\prime \prime}. From this and δ=δδ\delta=\delta^{\prime} \delta^{\prime \prime}, it follows that η=δδ\eta=\delta^{\prime} \delta^{\prime \prime}, i.e., (δ,δ)=1\left(\delta^{\prime}, \delta^{\prime \prime}\right)=1. Proof completed.
1(ab)8(ab)σ6a8δ(modm),\begin{array}{l} 1 \equiv(a b)^{8} \equiv(a b)^{\sigma^{6}} \\ \equiv a^{8 \delta^{\circ}}(\bmod m), \end{array}

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.