3
$\begingroup$

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

  • 0
    You could try to have a look at [Linear congruence theorem](http://en.wikipedia.org/wiki/Linear_congruence_theorem) at wiki, or [Solution of Linear Congruence](http://www.proofwiki.org/wiki/Solution_of_Linear_Congruence) at ProofWiki.2012-06-21

4 Answers 4

1

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.

  • 0
    Do you know a formula to calculate $x$ as well?2012-06-22
0

$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

0

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$

0

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