# How do I prove exchangeable modularity?

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

-
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

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.

-
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

-

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$

-

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).$

-