Menu
we know that
(A + B) % P = (A % P + B % P) % P (A * B) % P = (A % P * B % P) % P where P is a prime .
I need to calculate (A / B) % P where A,B can be very large and can overflow .
Does such kind of formula for modular arithmetic holds for (A / B) % P and (A - B) % P.
If not then please explain what the correct answer is.
I.e is it true that (A / B) % P = ((A % P) / (B % P)) % P?
I WAS TRYING TO CALULATE (N*(N^2+5)/6)%P where N can be as large as 10^15
here A=n*(n^2+5) can surely overflow for n=10^15
220
The modulus operator returns the remainder of a division of one number by another. In most programming languages, modulo is indicated with a percent sign. For example, "4 mod 2" or "4%2" returns 0, because 2 divides into 4 perfectly, without a remainder.
Most programming languages adopt the convention that the modulo operator (denoted by % rather than mod ) occupies the same place in the order of operations as multiplication and division. Hence, it comes AFTER the operations in parentheses, but BEFORE addition and subtraction.
2 mod 3 equals 2, since 2/3 = 0 with a remainder of 2. To find 2 mod 3 using the modulus method, we first find the highest multiple of the divisor, 3 that is equal to or less than the dividend, 2.
Modulo is a math operation that finds the remainder when one integer is divided by another. In writing, it is frequently abbreviated as mod, or represented by the symbol %.
Yes, but it's different:
(a - b) mod p = ((a mod p - b mod p) + p) mod p (a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p Where b^(-1) mod p is the modular inverse of b mod p. For p = prime, b^(-1) mod p = b^(p - 2) mod p.
Edit:
(N*(N^2+5)/6)%P
You don't need any modular inverses from this. Just simplify the fraction: N or N^2+5 will be divisible by 2 and 3. So divide them and then you have (a*b) mod P.
77
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
