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.

It is quite easy to evaluate $\frac{a}{b}\bmod m$ when $a$, $b$ and $m$ are integers and $\gcd(b,m)=1$ by replacing $\frac{1}{b}$ with an inverse of $b$ modulo $m$.

But, is it possible to evaluate that when $\gcd(b,m)\neq1$? For example I tried to find $\frac{16}{7}\bmod 7$ following way:

We are actually to find some $x$ such that $\frac{16}{7}\equiv x \pmod 7$
As modular arithmetic permits multiplication$16\equiv 7x \pmod 7$
But, $7x\equiv0 \pmod 7$
Hence $16\equiv0 \pmod 7$ which is absolutely wrong.

What wrong am I doing or should I conclude no such $x$ exists?

share|improve this question
5  
$7\equiv0 \mod 7$ so you are in effect trying to divide by zero. –  Henry Dec 12 '11 at 20:10
    
Exactly, no such $x$ exists. –  Thomas Andrews Dec 12 '11 at 20:21
add comment

4 Answers

There is no such thing as division by $b$ mod $m$ if $\text{gcd}(m,b) \ne 1$. $a/b = c \mod m$ should mean $a = b c \mod m$, but the value of $c$ mod $m$ (if it exists) would not be unique, because you could add $m/p$ to $c$ and get another solution, where $p$ is a common factor of $b$ and $m$.

share|improve this answer
    
Why value of $c$ won't be unique mod $m$? If we add $m/p$ to c we get $(c+m/p)$ but still $b(c+m/p)\equiv bc(\mod m)$. –  f.nasim Dec 12 '11 at 20:34
    
If there's another value, the value is not unique. That's what "not unique" means. –  Robert Israel Dec 13 '11 at 1:04
add comment

If $\mathrm{gcd}(b,m) \not=1$, then it is impossible to find integers $x,y \in \mathbb{Z}$ such that $bx+my=1$. Thus $b^{-1}$ does not exist "mod $m$".

If you try to give meaning to $1/b$ anyway, you will run into trouble. The problem is any $b$ which is not relatively prime to $m$, is either $0$ or a zero divisor mod $m$. This means that there is some $k \in \mathbb{Z}$ such that $k \not\equiv 0$ mod $m$ and $bk \equiv 0$ mod $m$. Thus if you allow $1/b$, then $k = 1\cdot k = (1/b)b \cdot k \equiv (1/b)0 = 0$ mod $m$. So now $k \equiv 0$ mod $m$ even though we assumed $k \not\equiv 0$ mod $m$. That's a contradiction.

share|improve this answer
add comment

HINT $\ $ Yes, $\ 16/7\ $ cannot exist since $\rm\ n/7\ \in\ \mathbb Z\ mod\ 7\ \Rightarrow\ n\ \equiv\ 7\ (n/7)\ \equiv\ 0\:.\:$ More generally

LEMMA $\ $ If $\rm\ x = a/b\ $ exists $\rm\:mod\ m\:,\:$ then any common divisor $\rm\:d\:$ of $\rm\:b\:$ and $\rm\:m\:$ must divide $\rm\ a\:,\:$ and $\rm\ d\:$ can be cancelled from $\rm\:a,b\:$ and $\rm\:m\:.\ $

Proof $\rm\ \ x\: \equiv\: a/b\pmod{m}\ $ implies $\rm\ m\ |\ b\ x - a\:.\:$ Thus $\rm\ d\ |\ m,\:b\ \Rightarrow\ d\ |\ a\:.\: $ Cancelling $\rm\:d\:$ yields $\rm\ m/d\ |\ b/d\ x - a/d\ $ i.e. $\rm\ \bar m\ |\ \bar b\ x \: -\: \bar a\:,\ $ $\rm\ x\:\equiv\: \bar a/\bar b \pmod{\bar m}\ $ where $\rm\ \bar m,\:\bar a,\:\bar b\ =\ m/d,\:a/d,\: b/d\:. $

So $\rm\ a/b\:$ exists $\rm\:mod\ m\ $ iff $\rm\ d = \gcd(b,m)\ |\ a\:,\:\: $ since then $\rm\:\: \gcd(\bar b,\bar m) = 1\ $ so $\rm\ 1/{\bar b}\ $ exists $\rm\:mod\ \bar m\:.\:$

See also this answer for a view from the standpoint of linear algebra.

share|improve this answer
add comment

In any finite commutative ring, every nonzero element is either a zero-divisor or a unit. So, if $\gcd(b,m)\not=1$, then $b$ is a zero-divisor in $\mathbb{Z}_m$. So, there exists $x\in \mathbb{Z}$ with $x\not \equiv 0\mod(m)$ such that $bx\equiv 0 \mod(m)$.

If $b$ were to be a unit in $\mathbb{Z}_m$, then we'd have $u\in \mathbb{Z}$ such that $ub\equiv 1 \mod(m)$. But then $0\equiv (bx)u\equiv x(bu)\equiv x \mod(m)$, a contradiction.

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.