0
$\begingroup$

If $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$, are there any conditions under which we can conclude that $a \equiv 1 \pmod{mn}$?

Here $m$ and $n$ are any integers; $a$ and $b$ are both coprime to $mn$.

$\endgroup$
  • $\begingroup$ It is sufficient for $n=1$, of course, and not necessarily true in any greater generality. $\endgroup$ – hardmath Aug 17 '14 at 1:00
  • $\begingroup$ Are $m$ and $n$ any integers? Prime? Coprime? $\endgroup$ – Mike Aug 17 '14 at 1:01
  • $\begingroup$ m and n are any integers. a and b are both coprime to mn. $\endgroup$ – Mike Aug 17 '14 at 1:11
  • $\begingroup$ Important information (such as your comment about $a $ being coprime to $mn$, which did not follow from the question) should be edited into the question, not left in a comment. $\endgroup$ – user147263 Aug 17 '14 at 4:14
  • 1
    $\begingroup$ This question is missing key information: (1) what is the context or background where you came upon the question; (2) what have you tried, or why do the solution methods you know not work? This information helps others write answers that are more useful to you. Questions without this info are likely to be put "on hold". $\endgroup$ – Carl Mummert Aug 17 '14 at 4:22
0
$\begingroup$

We know that we can find integers $k,\ell$ such that

$$a = b + km$$ $$b = 1+ \ell mn$$

Hence,

$$a = 1+\ell mn+km = 1 + (\ell n+k)m$$

So if we want $a \equiv 1 \pmod{mn}$ then we need $\ell n+k \equiv k \equiv 0 \pmod{n}$. Hence

$$a \equiv b \pmod{mn}$$

$\endgroup$
  • 1
    $\begingroup$ Given that $b \equiv 1 \pmod{mn}$, it's immediate that $a \equiv 1 \pmod{mn}$ if and only if $a \equiv b \pmod{mn}$. While this certainly gives conditions for the statement to hold, it seems like the OP is probably seeking something less tautological. $\endgroup$ – vociferous_rutabaga Aug 17 '14 at 1:21
  • $\begingroup$ To conclude $\ell n + k \equiv k \equiv 0 (\mod n)$ don't you need to assume $m$ and $n$ are coprime? $\endgroup$ – NovaDenizen Aug 17 '14 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.