1

I used to participate in programming competitions and at times I see that the solution should be the remainder when divided with some big prime number (usually that would be 1000000007). In one of the problems, I need to divide a very big number by another very big number and find the modulo of the division. Say one of the big numbers is factorial of 10000. So, the actual problem is how can I find the solution to

$$((A*B*C...)/(a*b*c*...))mod 1000000007$$

where the numerator and denominator are so huge.

I tried this by hand and it holds good.

$$(2 * 3 * 4 * 5) mod 7 = (((((2 mod 7 * 3) mod 7) * 4) mod 7) * 5) mod 7$$

  1. I would like to know, whether it will be True always. If so I will find the numerator and denominator values with this method.

Now, the second part, is division.

$$(A / B) mod C = ((A mod C)/(BmodC))modC$$

I thought that the above equation would be true. But it doesnt work for,

$$(((2*3)mod5)/(1*2)mod5)mod5\ne((2*3)/(1*2))mod5$$

So, how can I find value for the expression which I mentioned at the beginning?

thefourtheye
  • 175

4 Answers4

6

The way to divide by a number $a$ $(\bmod p)$ is to multiply by its inverse. To find its inverse, you can use the extended Euclidean algorithm.

In your example, we are dividing by $2$ modulo $5$. We calculate

$$5 = 2 \cdot 2 + 1$$ and have found the gcd of $2$ and $5$ after one step of the algorithm.

Now write $1 = 5 - 2 \cdot 2$ and reduce modulo $5$, to get $$1 \equiv (-2) \cdot 2 \equiv 3 \cdot 2 \, (\bmod 5),$$ so $2^{-1} \equiv 3 (\bmod 5).$ In particular, you have $$6 / 2 \equiv 6 \cdot 3 \equiv 1 \cdot 3 \equiv 3 (\bmod 5).$$

For a more difficult example, consider $123456/192$ modulo $17$.

We first reduce $192 \equiv 5 (\bmod 17)$. Now we calculate the inverse of $5$ mod $17$: $$17 = 3 \cdot 5 + 2,$$ $$5 = 2\cdot 2 + 1,$$ and so $$1 = 5 - 2 \cdot 2 = 5 - 2(17 - 3 \cdot 5) =7 \cdot 5 - 2 \cdot 17.$$ This gives $7 \cdot 5 \equiv 1 (\bmod 17)$, so $5^{-1} = 7$.

Now $123456/192 \equiv 123456 \cdot 5^{-1} \equiv 123456 \cdot 7 \equiv 2 \cdot 7 \equiv 14$ (modulo $17$).

In fact, $123456/192 = 643 = 37 \cdot 17 + 14$, so it checks out.

Cocopuffs
  • 10,307
  • Thanks @Cocopuffs. I think I can implement this for the division part. How about the first part (2∗3∗4∗5)mod7=(((((2mod7∗3)mod7)∗4)mod7)∗5)mod7? Will it be true always? – thefourtheye Jul 06 '13 at 07:51
  • 1
    @thefourtheye Yes. It's enough to look at a product of two. Look at integers $(a+7m)$ and $(b+7n)$: their product $ab + 7(mb+an+7mn)$ also reduces to $ab$ modulo $7$, so you would get the same if you reduce first and then multiply. – Cocopuffs Jul 06 '13 at 08:13
  • Thanks. I tried with few examples and convinced myself that its true. How about division? (A/B)modC=((AmodC)/(BmodC))modC? – thefourtheye Jul 06 '13 at 08:16
  • @thefourtheye Since $A/B = n$ if and only if $A = n \cdot B$, this is true for the same reason – Cocopuffs Jul 06 '13 at 08:19
  • You mean, it might not be true always? – thefourtheye Jul 06 '13 at 08:23
  • @thefourtheye The only problem that could happen is if $A$ and $B$ both have common factors with $C$, in which case you need to cancel them first – Cocopuffs Jul 06 '13 at 08:24
  • But it doesnt work when A=6, B=2 and C=5 :( – thefourtheye Jul 06 '13 at 08:26
  • 2
    @thefourtheye This is the first example I gave you. It works with the proper interpretation of $1/2 := 2^{-1}$ modulo $5$. Since $2 \cdot 3 = 1$ mod $5$, you need to understand $1/2$ as $3$. – Cocopuffs Jul 06 '13 at 08:28
  • Thanks @Cocopuffs, for clarifying all my doubts with patience. Looks like I got the idea. Let me try that in the program. – thefourtheye Jul 06 '13 at 08:31
1

I believe that your fraction is actually an integer, otherwise it does not make too much sense to find the remainder modulo 1000000007. If this is the case you should exploit this fact and make the semplifications as to eliminate the denumerator in your expression.

Also, the fact the the modulus is choosen to be a prime number, suggests that you might also try to incorporate this result: $$ a^p = a \pmod p $$ which should greatly simplify some kind of expressions.

Emanuele Paolini
  • 21,447
1

First of all, for any kind of integer $n \geq 2$, $\mathbb{Z} \xrightarrow{\ k\, \mapsto\, k \bmod n\ } \mathbb{Z}_n$ is a ring homomorphism which roughly means that all the ring operations will hold, and that includes addition, substraction and multiplication. In general division does not work this way, the simplest example is that (please ignore the fact that we are dividing by zero there...)

$$n \equiv_n 0 \quad \text{ while } \quad (n/n) \equiv_n 1 \not\equiv_n 0 \equiv_n (0/n).$$

However, you are doing modulo arithmetic with $p$ being prime, and that greatly simplifies things, because $\mathbb{Z}_p$ is a field which besides ring operations includes also division. The reciprocal $\frac{1}{n}$ of $n$ is an element such that $\frac{1}{n}\cdot n = 1$. In $\mathbb{Z}_p$ there are no fractions, but since $p$ is prime, from the Euclidean algorithm we know that there exists $m$ such that $m\cdot n \equiv_p 1$. Such $m$ will behave exactly like the reciprocal we are looking for.

So, if you want to calculate your numbers the hard way, then first get $n = A*B*C*\ldots \bmod p$, then $m = a*b*c*\ldots \bmod p$, then obtain the reciprocal $m^{-1}$ of $m$ using Euclidean algorithm, and finally the result $n*m^{-1} \bmod p$.

I hope this helps ;-)

dtldarek
  • 37,381
0

First, a little remark about notation. There are two common usages for the symbol "mod". The first usage, very common in mathematics, is like this: $$ a \equiv b \mod p $$ which means that $a-b$ is divisible by $p$. The second way is the way you used it, and the way it is used in many programming languages. This way $a\ \mathrm{mod}\ b$ means the remainder of $a$ when divided by $b$. Since we're on a math forum, I'll use "mod" in the first way. For the remainder, I'll use "%", as in the C language.

Now, for your first question. What you're asking is a proof for this equality: $$ (x_1 x_2 \ldots x_n) \% p = (\ldots((x_1 \% p) \cdot x_2) \% p \cdot \ldots \cdot x_n) \% p. $$

Your equality holds because of the following important property of congruence modulo $p$:

Proposition 1. If $a_1, a_2, b_1, b_2$ are integers and $p$ is a non-zero integer, and $$ a_1 \equiv a_2 \mod p \quad \mathrm{and} \quad b_1 \equiv b_2 \mod p, $$ then also $$ a_1 b_1 \equiv a_2 b_2 \mod p. $$ Proof. By definition, $a_2-a_1 = pm$ and $b_2 - b_1 = pn$, where $m$ and $n$ are integers. Then $$ a_2 b_2 = (a_1 + pm)(b_1 + pn) = a_1b_1 + p(mb_1 + na_1 + pmn). $$ It follows that $a_2b_2 - a_1b_1$ is divisible by $p$, so $$ a_1 b_1 \equiv a_2b_2 \mod p,\quad \mathrm{QED.} $$

Now, to prove your equality. Start with two numbers $x_1$ and $x_2$. It is easy to see that $x_1 \equiv x_1\%p \mod p$ and $x_2 \equiv x_2 \mod p$. Then by proposition 1 we have $$ x_1 x_2 \equiv (x_1 \%p) \cdot x_2 \mod p, $$ from which it follows that $$ x_1 x_2 \equiv ((x_1 \%p) \cdot x_2)\%p \mod p. $$ Now we add $x_3$. Using the last equivalence, and the fact that $x_3 \equiv x_3 \mod p$, and proposition 1, we get $$ x_1 x_2 x_3 \equiv (((x_1 \% p) \cdot x_2)\%p)\cdot x_3 \mod p, $$ which implies $$ x_1 x_2 x_3 \equiv ((((x_1 \% p) \cdot x_2)\%p)\cdot x_3)\%p \mod p, $$ We can repeat this reasoning (technically, this should be framed as a proof by induction). In the end we will come to the following: $$ x_1 x_2 \ldots x_n \equiv ((((x_1 \% p) \cdot x_2)\%p)\cdot \ldots \cdot x_n)\%p \mod p. $$ Your equality follows immediately if you replace the left hand side by its remainder modulo $p$.

A similar kind of logic can be used to justify any similar equality for an expression that involves only operations $+$, $-$ and $*$ (note that division is not in this list). For instance $$ ((a+b)(c+d))\%p \equiv (a\%p + b\%p)((c+d)\%p) \mod p. $$

You can replace any part of an expression by its remainder modulo $p$, and it will not change the remainder of the expression as a whole.

I would suggest looking into the subject of modular arithmetic to get the hang of all this. It is way easier to understand when you have a basic understanding of such concepts as equivalence relations, groups, group homomorphisms, rings and ring homomorphisms.

After that it will become much easier to understand the deal with division, which I haven't mentioned at all. I think the answer is lengthy enough as it is.

Dan Shved
  • 15,862
  • 39
  • 55