Hint: Use LTE method, and use the prime factorization of $n$.

Let $n=\Pi_{i=1}^{k}{p_i^{a_i}}$ Let $b$ is positive integer greater than $\max_{i=1}^{k} \{ v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) +v_{p_i} (m^{p_i-1}-1)\}$ Choose $a=\prod_{i=1}^{k}{(p_i^{k_i}(p_i-1))}$ where $k_i=ba_i-\Big( v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) +v_{p_i} (m^{p_i-1}-1) \Big) >0$ for all $i=1,2,...,k$ Then we have $v_{p_i} (m^a-1) =v_{p_i} (m^{p_i-1}-1) +v_{p_i} \Big( p_i^{k_i}\Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) \Big) =ba_i=bv_{p_i}(n)$ So $gcd(\frac{m^a-1}{n^b},n)=1$ which mean $gcd(c,n)=1$

ThE-dArK-lOrD wrote: Then we have $v_{p_i} (m^a-1) =v_{p_i} (m^{p_i-1}-1) +v_{p_i} \Big( p_i^{k_i}\Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) \Big)$ . I think we should check the precondition of LTE here,$(n,m)=1$,so $(p_i,m)=1$,for all $p_i$,by FLT,we have $p_i|m^{p_i-1}-1$,for all $p_i$.

ThE-dArK-lOrD wrote: Let $n=\Pi_{i=1}^{k}{p_i^{a_i}}$ Let $b$ is positive integer greater than $\max_{i=1}^{k} \{ v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) +v_{p_i} (m^{p_i-1}-1)\}$ Choose $a=\prod_{i=1}^{k}{(p_i^{k_i}(p_i-1))}$ where $k_i=ba_i-\Big( v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) +v_{p_i} (m^{p_i-1}-1) \Big) >0$ for all $i=1,2,...,k$ Then we have $v_{p_i} (m^a-1) =v_{p_i} (m^{p_i-1}-1) +v_{p_i} \Big( p_i^{k_i}\Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big) \Big) =ba_i=bv_{p_i}(n)$ So $gcd(\frac{m^a-1}{n^b},n)=1$ which mean $gcd(c,n)=1$ If p=2,how can you do like this?

@llpllp. For $n$ is even,$m$ is odd,if $m\equiv 1(mod4)$,the-dark-lord's argument holds. Remain case $m=3(mod4)$,choose $b=\max_{i=1}^{k} \{ v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big)+v_2(m-1)+v_2(m+1))+1$ as darklord,choose $k_i=ba_i-\Big( v_{p_i} \Big( \frac{\Pi_{j=1}^{k}{(p_j-1)}}{p_i-1} \Big)+v_2(m-1)+v_2(m+1))-1 \big)$.Which satisfy the condition.

Is this solution acceptable? It is suffice to prove that $n|{m}^{a}-1$ since a, b and c are positive integers. This can be rewritten as ${m}^{a}=1(mod n)$. By Euler's Theorem, $a|phi(n)$

DA2004 wrote: Is this solution acceptable? It is suffice to prove that $n|{m}^{a}-1$ since a, b and c are positive integers. This can be rewritten as ${m}^{a}=1(mod n)$. By Euler's Theorem, $a|phi(n)$ Do you mean $\phi$?

JustKeepRunning wrote: DA2004 wrote: Is this solution acceptable? It is suffice to prove that $n|{m}^{a}-1$ since a, b and c are positive integers. This can be rewritten as ${m}^{a}=1(mod n)$. By Euler's Theorem, $a|phi(n)$ Do you mean $\phi$? Yes. Is my solution right?

$c$ has to be relatively prime, not just a positive integer so your solution wouldn't work (and this is the main part of the problem).

Nice problem... Step 1: Let $a=O_n(m) \cdot k => n \mid m^a -1$. Step 2: Write $n=p_1^{\alpha_1} p_2^{\alpha_2}...p_j^{\alpha_j}$. Thus, by LTE, we get $v_{p_i}(m^{O_n(m)}-1)+v_{p_i}(t)= b \cdot \alpha_i$ for all $i$ from $[1,2,...,j]$. Step 3: Just notice that you can tweak $v_{p_i}(t)$ without affecting $v_{p_l}(t)$ for $p \neq l$- thus just set $b$ big enough such $b \geq v_{p_i}(m^{O_n(m)}-1)$ for all $i$ from $[1,2,...,j]$, and then set $v_{p_i}(t) = b \cdot \alpha_i - v_{p_i}(m^{O_n(m)}-1) => v_{p_i}(c)=0$ and we're done? Can someone verify if this works- seems like suspiciously easy construction for a problem from China...

fattypiggy123 wrote: $c$ has to be relatively prime, not just a positive integer so your solution wouldn't work (and this is the main part of the problem). Does it matter? Because we can consider $c$ as the part of the prime factorization of ${m}^{a}-1$ that is not divisible by $n$. $c$ can be 1 anyways.

Well... look at it this way- say $m^a -1 \equiv 0 \mod{n}$ but is $pn \mod{n^2}$, where $p \mid n$. I see it could be hard to understand abstractly, so here's an example- take $m=25$, $n=6$. Here we have $m^1 -1 \equiv 0 \mod{6}$, therefore we meet all your conditions, yes? But, trying to equate it we get $25-1=6^1 \cdot 4$, hence $(6,4) \neq 1$. You see what I mean? You'll definitely need tighter constraints, and I'm pretty sure the ones in #12 work- there, I used $O_n(m)$, but honestly I could have used $\phi(m)$ or really any multiple of $O_n(m)$

What does this function do $O_n(x)$?

Oh... well for this solution, the only thing you need to know is that $O_n(m)$ is the smallest positive integer such that $m^{O_n(m)}=1 \mod{m}$ for co-prime $(m,n)$. If you want to know more about orders, you could always check out Evan Chen's handouts on the topic, although it's really not necessary for this problem.

Let $m^{\phi(n)}=t$.By Euler's theorem $n\mid t-1$. Let $n=2^sp_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$. Then pick a large integer $K$.Let $$c_i=Ka_i-v_{p_i}{(t-1)}$$and $\ell=Ks-v_2(t-1)-v_2(t+1)+1$.Now pick $$b=2^{\ell}p_1^{c_1}p_2^{c_2}\dots p_r^{c_r}$$Then by $\emph{LTE} $ it is easy to see, $t^b-1=m^{b\phi(n)}-1=n^Kc$ for some $c$ and $\gcd(n,c)=1$. $\blacksquare$

Let $\{p_i\}$ be the set of prime factors if $n$.Let $N=\prod {(p_i-1)}$.Then $p_i|m^N-1$.Let $v_i =v_{p_i}(m^N-1)$.We will $a$ to be a number of the form $k.N$.Now $$v_{p_i}(m^{kN}-1)=v_i +v_{p_i}k$$Now take a large enough $b$ such that $b\times v_{p_i}n -v_i$ is positive for all $i$.And put $$v_{p_i}k=b\times v_{p_i}n -v_i$$for all $i$ and formulate a suitable $k$.

Commit to having $\varphi(n) \mid a$ and rewrite the equation as $m^{\varphi(n)d}-1=cn^b$. Pick a massive integer $N$, and pick $d$ such that for each $p \mid n$, we have $\nu_p(d)=N\nu_p(n)-\nu_p(m^{\varphi(n)}-1)$. Then by exponent lifting (since $p \mid n \mid m^{\varphi(n)}-1$), the LHS has $\nu_p$ equal to $N\nu_p(n)$ for any such $p$. As such, we may select $b=N$, and then the corresponding value of $c$ will be coprime to $n$. $\blacksquare$