Let $n$ be a positive integer with $n = p^{2010}q^{2010}$ for two odd primes $p$ and $q$. Show that there exist exactly $\sqrt[2010]{n}$ positive integers $x \le n$ such that $p^{2010}|x^p - 1$ and $q^{2010}|x^q - 1$.
Problem
Source: 2010 Indonesia TST stage 2 test 5 p4
Tags: number theory
17.12.2020 06:45
Straightforward. It is evident that $(x,p\cdot q)=1$. Now, using LTE, $v_p(x^p-1)=v_p(x-1)+v_p(p)=1+v_p(x-1)\ge 2010$. Hence, $x\equiv 1\pmod{p^{2009}}$. Likewise, $x\equiv 1\pmod{q^{2009}}$. By CRT, $x\equiv 1\pmod{p^{2009}q^{2009}}$. Set now $x=\ell \cdot p^{2009}\cdot q^{2009}+1$, $0\le \ell<pq$. There are $pq$ such $\ell$'s; hence $pq$ such $x$'s. Since $pq=\sqrt[2010]{n}$, we are done.
17.12.2020 09:47
grupyorum wrote: Now, using LTE, $v_p(x^p-1)=v_p(x-1)+v_p(p)=1+v_p(x-1)\ge 2010$. No, you have to estabilish first that $p\mid x-1$ to use LTE. EDIT: An unnecessarily overcomplicated statement was here. See below.
17.12.2020 16:24
XbenX wrote: grupyorum wrote: Now, using LTE, $v_p(x^p-1)=v_p(x-1)+v_p(p)=1+v_p(x-1)\ge 2010$. No, you have to estabilish first that $p\mid x-1$ to use LTE. But there is a way out of this. In the set $\{1,2,\dots,p^{2010}\}$ the number of $x$s that satisfy $x\equiv 1 \pmod {p^{2009}}$ is $p$. It is well-known that there is a primitive root modulo $p^{2010}$, say $g$. So, we're trying to find $1\leq k\leq \varphi(p^{2010})$ such that $x=g^{pk}\equiv 1\pmod {p^{2010}}$ which implies that $\varphi(p^{2010})\mid kp$, or equivalently $p^{2009}-p^{2008}\mid k$. There are $\left [\frac{p^{2010}-p^{2009}}{p^{2009}-p^{2008}}\right]=p$ such $k$, which implies that $x$s such that $x\equiv 1\pmod{p^{2009}}$ are all numbers that satisfy that condition. Well, $x^p\equiv x\pmod{p}$. Hence $p^{2010}\mid x^p-1\implies p\mid x^p-1\implies p\mid x-1$
17.12.2020 16:25
Yes, thats easier. But if you don't state that, the proof makes no sense. @below, that is a matter of opinion. I have no doubt you knew what you were doing, as indeed that was trivial, but writing 'Obviously $x\equiv 1 \pmod p$' would've saved me some time as I thought you were implying LTE just because of the $\gcd(x,p)=1$ relation. Peace
17.12.2020 16:39
XbenX wrote: Yes, thats easier. But if you don't state that, the proof makes no sense. Well, no. Immediate steps are often swept under rug.