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

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|cite|improve this question
$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

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|cite|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

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|cite|improve this answer

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|cite|improve this answer

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