Let $a,m$ be positive integers such that $Ord_m (a)$ is odd and for any integers $x,y$ so that 1.$xy \equiv a \pmod m$ 2.$Ord_m(x) \le Ord_m(a)$ 3.$Ord_m(y) \le Ord_m(a)$ We have either $Ord_m(x)|Ord_m(a)$ or $Ord_m(y)|Ord_m(a)$.prove that $Ord_m(a)$ contains at most one prime factor.
Problem
Source: Iranian third number theory finals problem 3
Tags: number theory
16.08.2019 21:20
The converse is also true even without the condition of $Ord_m(a)$ is odd.BTW the proof of the converse is much more easier than the original problem the only thing we need is to notice $Ord_m(a)| lcm (Ord_m(x),Ord_m(y))$.
20.08.2019 03:20
Assume for contradiction that $Ord_m(a)$ has at least two prime factors then we can write $Ord_m(a)=rs$ where $gcd (r,s)=1$ and $r,s$ are both greater than $1$.Now take a natural solution pair $(k,\ell )$ of the equation $ks+r \ell \equiv 1 \pmod {\varphi (m)}$(exists by bezout's theorem) and consider $(x,y)=(-a^{ks},-a^{r \ell })$ we claim this choice of $(x,y)$ will contradict the condition of problem.First of all: $xy \equiv a^{ks+r \ell} \equiv a \pmod m$ Where the last equality follows from Euler's Theorem.Now we tend to prove a key lemma: Lemma:Let $z,t$ be natural numbers so that $Ord_z (t)$ is odd then $Ord_z (-t)=2Ord_z (t)$. Proof of the Lemma:Let $Ord_z(t)=w$ then $(-t)^w \equiv -1 \pmod z$ and $(-t)^{2w} \equiv 1 \pmod z$ so $Ord_z(-t)=2q$ is even so if $q<w$ we have $t^{2q} \equiv 1 \pmod z$ so $w|2q$ and since $w$ is odd we have $w|q$ which is clearly a contradiction hence the lemma. From the lemma it is easy to see $Ord_m(x)=2r,Ord_m(y)=2s$ which is clearly a contradiction hence $Ord_m(a)$ has at most one prime factor.
02.03.2022 04:38
Lemma 1: If for $a,b$ such that $(a,n)=(b,n)=1$ and $(ord_n(a),ord_n(b))=1$ then we have $$ ord_n(ab)=ord_n(a) \cdot ord_n(b) $$ Lemma 2: Suppose that $ord_m(a)=t$ and $u$ be a positive integer. Then $$ ord_m(a^u)= \frac{t}{gcd(t,u) } $$ Proof We have $(a^u)^{\frac{t}{gcd(t,u)}}=a^{lcm(t,u)} \equiv 1 \pmod m$ since $t=ord_m(a) \mid lcm(t,u)$. Now suppose that there exists $k<\frac{t}{gcd(t,u)}$ such that $a^{uk} \equiv 1 \pmod p$, then $$ t=ord_m(a) \mid {uk} \implies {\frac{t}{gcd(t,u)}} \mid k \text{ (Contradiction) } $$ Now suppose that $ord_m(a)$ has more than $2$ prime factors, then $ord_m(a)=u \cdot v$ for $(u,v)=1$ Then by Bezout, there exists $h,k$ such that $$ hu+kv \equiv 1 \pmod {\varphi(m)} $$Let choose $(x,y)=(-a^{hu},-a^{kv})$ then by lemma 2 we have $ord_m(-x)=ord_m(a^{hu})=\frac{ord_m(a)}{(ord_m(a),hu)}=v$ $$ xy \equiv (-a^{hu}) \cdot (-a^{kv}) \equiv a^{hu+kv} \equiv 1 \pmod m $$Now since $(-1,m)=(a^{hu},m) =1$ and $(ord_m(-1),ord_m(a^{hu}))=(v,2)=1$ then by lemma 1 $$ ord_m(-a^{hu})=ord_m(-1) \cdot ord_m(a^{hu})=2v $$Similarly $ord_m(-a^{kv} ) = 2u$, but since at least $1$ of $ord_m(x),ord_m(y)$ divides $ord_m(a)$, we have a contradiction