Given positive odd integers $m$ and $n$ where the set of all prime factors of $m$ is the same as the set of all prime factors $n$, and $n \vert m$. Let $a$ be an arbitrary integer which is relatively prime to $m$ and $n$. Prove that: \[ o_m(a) = o_n(a) \times \frac{m}{\gcd(m, a^{o_n(a)}-1)} \]where $o_k(a)$ denotes the smallest positive integer such that $a^{o_k(a)} \equiv 1$ (mod $k$) holds for some natural number $k > 1$.
Problem
Source: Indonesian Stage 1 TST for IMO 2022, Test 3 (Number Theory)
Tags: Order, number theory, identity, Divisibility
26.12.2021 00:13
Let $p$ be a prime dividing $n$. Note that $o_n(a)|o_m(a)$ and $v_p(a^{ko_n(a)}-1)=v_p(a^{o_n(a)}-1)+v_p(k)$. Therefore if $v_p(a^{o_n(a)}-1)\geq v_p(m)$ we don't need any factors of $p$ in $k$ but otherwise we must have $p^{v_p(m)-v_p(a^{o_n(m)}-1)}=p^{v_p(\frac{m}{\gcd(m,a^{o_n(a)}-1)})}$ Therefore $\frac{m}{\gcd(m,a^{o_n(a)}-1)}|k$ which is sufficient, so the result follows
04.03.2022 04:26
Does anyone has a more clear solution? I cannot follow the previous post.
04.03.2022 23:03
Indonesia TST-01 2022 Test 3/NT wrote: Given positive odd integers $m$ and $n$ where $\text{rad}(m) = \text{rad}(n)$, and $n \vert m$. Let $a$ be an arbitrary integer which is relatively prime to $m$ and $n$. Prove that: \[ o_m(a) = o_n(a) \times \frac{m}{\gcd(m, a^{o_n(a)}-1)} \]where $o_k(a)$ denotes the smallest positive integer such that $a^{o_k(a)} \equiv 1$ (mod $k$) holds for some natural number $k > 1$. Claim 01. $o_n(a) \mid o_m(a)$ Proof. Note that $n \mid m \mid a^{o_m(a)} - 1 \implies o_n(a) \mid o_m(a)$. Claim 02. $\frac{m}{\gcd(m,a^{o_n(a)} - 1)} \mid \frac{o_m(a)}{o_n(a)}$. Proof. It suffices to prove this $\nu_p(m) - \min \{ \nu_p(m) , \nu_p(a^{o_n(a)} - 1) \} \le \nu_p(o_m(a)) - \nu_p(o_n(a))$ for every prime $p \mid n$. There are two cases: If $\nu_p(m) \le \nu_p(a^{o_n(a)} - 1)$, then it suffices to prove that $\nu_p(o_m(a)) - \nu_p(o_n(a)) \ge 0$, which must be true as $o_n(a) \mid o_m(a)$. If $\nu_p(m) > \nu_p(a^{o_n(a)} - 1)$, then as $p$ is odd, by LTE, \begin{align*} \nu_p \left( \frac{o_m(a)}{o_n(a)} \right) &= \nu_p(a^{o_n(a) \cdot \frac{o_m(a)}{o_n(a)}} - 1) - \nu_p(a^{o_n(a)} - 1)\\ &= \nu_p(a^{o_m(a)} - 1) - \nu_p(a^{o_n(a)} - 1) \\ &\stackrel{m \mid a^{o_m(a)} - 1}{\ge} \nu_p(m) - \nu_p(a^{o_n(a)} - 1) \end{align*}which is what we wanted. Claim 03. $o_m(a) \mid o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} - 1)}$. Proof. We aim to prove that $m \mid a^{o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} - 1)}} - 1$. Therefore, for all prime $p \mid m$, as $p$ must be odd, by LTE, we have \begin{align*} \nu_p( a^{o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} - 1)}} - 1)&= \nu_p(a^{o_n(a)} - 1) + \nu_p \left( \frac{m}{\gcd(m,a^{o_n(a)} - 1)} \right) \\ &= \nu_p(m) + \nu_p \left( \frac{a^{o_n(a) } - 1}{\gcd(m,a^{o_n(a)} - 1)} \right) \ge \nu_p(m) \end{align*}This gives us \[ m \mid a^{o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} -1}}-1 \implies o_m(a) \mid o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} - 1)} \]which is what we wanted. Combining both lemma above, we conclude that \[ o_m(a) = o_n(a) \cdot \frac{m}{\gcd(m,a^{o_n(a)} - 1)} \] Remark. A standard idea in proving $A = B$ in number theory is to prove that $A \mid B$ and $B \mid A$. Now, use the property of order and LTE to sort everything out.