is there result relating $(a b)^{x} \text { with } \bmod (m n)$?

75 Views Asked by At

$\begin{array}{l}{\text { if } \operatorname{gcd}(a, n)=1 \quad \& \operatorname{gcd}(b, m)=1} \\ {a^{x} \equiv s \bmod (n)} \\ {b^{x} \equiv s \bmod (m)} \\ {\text { is there result relating }(a b)^{x} \text { with } \bmod (m n) ? ?}\end{array}$

2

There are 2 best solutions below

0
On

Note that

$$a^{x} \equiv s \pmod n \iff a^x - s = jn \; \text{, for some} \; j \in \mathbb{Z} \tag{1}\label{eq1}$$ $$b^{x} \equiv s \pmod m \iff b^x - s = km \; \text{, for some} \; k \in \mathbb{Z} \tag{2}\label{eq2}$$

Multiplying \eqref{eq1} with \eqref{eq2}, and switching sides, gives

\begin{align} (jk)(mn) & = \left(a^x - s\right)\left(b^x - s\right) \\ & = a^x b^x - a^x s - sb^x + s^2 \\ & = \left(ab\right)^x - s\left(a^x + b^x - s\right) \tag{3}\label{eq3} \end{align}

Thus,

$$\left(ab\right)^x - s\left(a^x + b^x - s\right) \equiv 0 \pmod{mn} \iff \left(ab\right)^x \equiv s\left(a^x + b^x - s\right) \pmod{mn} \tag{4}\label{eq4}$$

As discussed in notation - What is the difference between $x \bmod y$ and $x \pmod y$?, if you're indicating a binary operation with the smallest positive remainder, i.e., so $0 \le s \lt n$ and $0 \le s \lt m$, instead of a congruence relation, and you want to determine the smallest such remainder for $\left(ab\right)^x$ when divided by $mn$, then it'll be the right side of \eqref{eq4} possibly adjusted (most likely reduced) by some multiple of $mn$. However, without having more information about what the various values are, I don't see any way to provide a more explicit answer.

1
On

Hint $ $ Specialize the following mixed modulus $ $ Product Rule

$\qquad \begin{align} x&\equiv s\!\!\pmod{\!n}\\ y&\equiv t\!\!\pmod{\!m}\end{align}\ $ $\Rightarrow\ xy\equiv st + (x\!-\!s)t + (y\!-\!t)s\ \pmod{mn}$

Proof $\ $ Expand $\, (x-s)(y-t)\equiv 0\pmod{\!mn}$