1

$\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}$

user373141
  • 2,503
  • 2
    In order to be able to stitch together information modulo $m$ and information modulo $n$ to information modulo $mn$, one usually requires $\gcd(m,n)=1$. Otherwise there cannot be any hope of a unique answer. Of course, multiple solutions is also a result. – Arthur Jul 15 '19 at 21:43
  • @Arthur yes gcd(m,n)=1 – user373141 Jul 15 '19 at 21:46
  • 1
    What values are considered known vs unknown? Do we know $a$ and $b$ as integers, or do we only know them as residues mod $n$ and $m$ respectively, or do we even not know what $a$ and $b$ are? – anon Jul 15 '19 at 22:17
  • Please confirm that want the same $s$ in both cases. – Bill Dubuque Jul 15 '19 at 22:26

2 Answers2

2

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.

John Omielan
  • 47,976
1

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}$

Bill Dubuque
  • 272,048