Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

4 Answers 4

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|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
add comment

$$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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.