Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I prove that, considering all numbers natural, and p and i relatively prime,

$mp+n \not \equiv 0 \pmod i$

is the same as

$m-x \not \equiv 0 \pmod i$

considering x a natural number and the solution of

$xp+n \equiv 0 \pmod i$ ?

share|cite|improve this question
You could try to have a look at Linear congruence theorem at wiki, or Solution of Linear Congruence at ProofWiki. – Martin Sleziak Jun 21 '12 at 12:01
up vote 1 down vote accepted

Since $p$ and $i$ are relatively prime, we know that $p$ has a multiplicative inverse mod $i$, which is to say there is a number $p^{-1}$ such that $p\,p^{-1}\equiv 1\pmod i$. If $x$ is a solution to $$ xp+n\equiv 0\pmod i $$ we can multiply both sides of the congruence above by $p^{-1}$ to obtain $$ x+p^{-1}n\equiv 0 \pmod i $$ Since we are also given that $m \not \equiv x\pmod i$ we have $$ m+p^{-1}n \not \equiv 0 \pmod i $$ Now, multiplying both sides of this by $p$ we obtain $$ mp+n\not \equiv 0 \pmod i $$ as required. This argument is reversible, so the two conditions in the original probem are equivalent.

share|cite|improve this answer
Thanks a lot, this is exactly what i needed! – user1043065 Jun 21 '12 at 13:43
Do you know a formula to calculate $x$ as well? – user1043065 Jun 22 '12 at 10:33

$$xp+n\equiv 0\pmod i\,\wedge\,m-x\equiv 0\pmod i\,\Longrightarrow \,m\equiv x\pmod i\,\Longrightarrow$$$$\Longrightarrow\,mp+n\equiv xp+n\pmod i\equiv 0 \pmod i $$and you can go back and forth with the arrows above

share|cite|improve this answer

Consider the two statements $mp+n \not\equiv 0 \pmod i$ and $xp+n \equiv 0 \pmod i$ and suppose that $m-x \equiv 0 \pmod i$

Since $m-x \equiv 0 \pmod i$ we know that $i\mid(m-x) \implies i\mid(m-x)k \ \ \ \ \forall k \in \mathbb{Z}$

Also, $(mp+n)-(xp+n)\not\equiv 0 \pmod i$ $\implies mp-xp \not\equiv 0 \pmod i$

Therefore $(m-x)p \not\equiv 0\pmod i \implies i \not\mid (m-x)p$

This is a contradiction, therefore $mp+n \not\equiv 0 \pmod i$ and $xp+n \equiv 0 \pmod i$ $\implies$ $m-x \not\equiv 0 \pmod i$

share|cite|improve this answer

Hint $\rm\,\ 0\not\equiv mp\!+\!n \equiv mp\!+\!n\!-\!(xp\!+\!n)\equiv (m\!-\!x)\,p.\:$ Scale this by $\rm1/p\:$ (exists by $\rm\:(p,i)=1).$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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