$\newcommand\ord{\text{ord}}$ For integers $n,m,p$, suppose $m$ and $n$ share the same prime divisors with $m$ dividing $n$, and suppose $\text{gcd}(p,n)=1$. I want to show that $\ord_n(p)/m=\ord_{n/m}(p)$, where $\ord_x(p)$ denotes the order of $p$ in the multiplicative group of integers modulo $x$. It's only my guess that this is true, and I'm wondering how to prove it. Edit: As `reuns' showed a counter-example in the comments for $\ord_{n/m}(p)>1$, I now only consider the question for $\ord_{n/m}(p)=1$.
But even the case $\ord_{n/m}(p)=1$ is difficult for me. Then $p = qn/m+1$ for a quotient $q$ from division by $n/m$. If $\ord_n(p)=1$ then $p=q'n+1$ for another quotient $q'$ (from division by n) in which case $q'=q/m$. Hence unless $q$ is divisible by $m$ we know $\ord_n(p)>1$. Henceforth we will actually assume $\text{gcd}(m,q)=1$. Now we'd like to show $m$ is the smallest $t$ for which $(qn/m+1)^t\equiv1(\bmod n)$. Using binomial expansion we write $$ \begin{align} (qn/m + 1)^t &= \sum_{k=0}^t \binom{t}{k}(qn/m)^k \\ &= 1 + tqn/m + \frac{t(t-1)}{2!}(qn/m)^2 + \dots + \frac{t(t-1)}{2!}(qn/m)^{t-2} + t(qn/m)^{t-1} + (qn/m)^t \end{align} $$ I'd like to assert that if the sum of all terms other than $1$ is divisible by $n$, it must be that each term other than $1$ is divisible by $n$. Is this true? Supposing that to be the case, if $n$ is to divide $tqn/m$ we must have $tq=\text{lcm}(q,m)=qm/\text{gcd}(q,m) = qm$ implying $t\geq m$. Now to show all terms other than the first two are also divisible by $n$ when $t=m$, I only know to further restrict criteria with $m^s=n$ for $s\geq2$. Then $(n/m)^k/n = m^{ks-k-s}$ and $ks-k-s\geq0$ for $k\geq2$, in which case all terms beyond the first two are indeed divisible by $n$, implying $\ord_n(p)=m$. For what other criteria can this equation be shown to hold? In particular, how about for $n$ not a power of $m$? How about for $p$ an odd prime? (Still supposing $\text{gcd}(m,q)=1$.)
$\newcommand\ord{\operatorname{ord}}\newcommand\lcm{\operatorname{lcm}}$ Consider integers $n,m,p$ with $m^2|n$. Suppose we have $p=q(n/m)+1$ for some integer quotient $q$ such that $\ord_{n/m}(p)=1$. Then $\ord_n(p)=m/\gcd(q,m)$.
We must show that the smallest integer $t$ for which $(qn/m+1)^t\equiv1(\bmod n)$ is $m$. Using binomial expansion we write $$ \begin{align} (qn/m+1)^t &= \sum_{k=0}^t \binom{t}{k}(qn/m)^k \\ = 1 &+ t(qn/m) + \frac{t(t-1)}{2!}(qn/m)^2 + \dots \\ &+ \frac{t(t-1)}{2!}(qn/m)^{t-2} + t(qn/m)^{t-1} + (qn/m)^t \end{align} $$ We must find the smallest $t$ for which $n$ divides all terms for $k\geq1$. With $r:= n/m^2$ we may represent the $k$'th term as $$ \begin{equation} n\binom{t}{k}q^k\frac{n^{k-1}}{m^k} = n\binom{t}{k}q^kr^{k-1}\frac{m^{2(k-1)}}{m^k} = n\binom{t}{k}q^kr^{k-1}m^{2k-2-k} \end{equation} $$ Since $2k-2-k\geq0$ for $k\geq2$ we have it that $n$ divides all terms for $k\geq2$. Therefore $n$ divides the sum of all terms for $k\geq1$ if and only if $n$ divides the term $t(qn/m)$. The smallest $tq$ for which $tq/m$ is an integer (and thus $n$ divides $t(qn/m)$) is $\lcm(q,m)$. Thus $\lcm(q,m)=qm/\gcd(q,m)$ is the smallest such $tq$ and it follows that $\ord_n(p)=t=m/\gcd(q,m)$.