mod, modp, mods
-- the modulo
functionsmodp(x, m)
computes the unique nonnegative remainder on
division of the integer x by the integer m.
mods(x, m)
computes the integer r of least
absolute value such that the integer x - r is divisible by
the integer m.
By default, x mod m
and _mod(x, m)
are
both equivalent to modp(x, m)
.
x mod m _mod(x, m)
modp(x, m)
mods(x, m)
x, m |
- | arithmetical expressions |
x
, m
By default the operator mod
and the function
_mod
are equivalent to modp
. This can be
changed by assigning a new value to _mod
; see
example 5.
/
, div
, divide
, Dom::IntegerMod
, frac
, gcd
, gcdex
, igcd
, igcdex
, IntMod
, powermod
modp
and
mods
return an integer r such that x = q*m
+ r holds for some integer q. In addition, we have
0 <= r < |m| for modp
and -|m|/2
< r <= |m|/2 for mods
. See example 2. These conditions uniquely define r in
both cases. In the modp
case, we have q = x div
m
.modp
and mods
both compute an integral
solution r of the congruence vr = u mod m. To
this end, they first compute an inverse w of v
modulo m, such that v*w - 1 is divisible by
m. This only works if v is coprime to
m, i.e., if their greatest common divisor is 1.
Then modp(u*w, m)
or mods(u*w, m)
,
respectively, as described above, is returned. Otherwise, if
v and m are not coprime, then an error message is
returned. See example 2.
The number x - modp(x, m)
is not an integral multiple
of m in this case.
modp
and mods
return an integer or a
rational number r such that x = q*m + r holds for
some integer q. In addition, we have 0 <= r <
|m| for modp
and -|m|/2 < r <=
|m|/2 for mods
, and these conditions uniquely define
r in both cases. See example 3._mod(x, m)
is the functional equivalent of the
operator notation x mod m
. See example 1._mod
is equivalent to
modp
.modp
and mods
can be used
to redefine the modulo operator. E.g., after the assignment
_mod:=mods
, both the operator mod
and the
equivalent function _mod
return remainders of least
absolute value. See example 5._mod
, modp
, and mods
are
kernel functions.The example demonstrates the correspondence between the
function _mod
and the operator mod
:
>> hold(_mod(23,5))
23 mod 5
>> 23 mod 5 = _mod(23,5)
3 = 3
Here are some examples where the modulus is an integer.
We see that mod
and modp
are equivalent by
default:
>> 27 mod 3, 27 mod 4, modp(27, 4), mods(27, 4)
0, 3, 3, -1
>> 27 = (27 div 4)*4 + modp(27, 4)
27 = 27
Let us now compute 22/3 modulo 5. The greatest common divisor of 3 and 5 is 1, and 2 is an inverse of 3 modulo 5. Thus 22/3 modulo 5 equals 22*2 modulo 5:
>> modp(22/3, 5) = modp(22*2, 5), mods(22/3, 5) = mods(22*2, 5)
4 = 4, -1 = -1
The greatest common divisor of 15 and 27 is 3, so that 15 has no inverse modulo 27 and the following command fails:
>> modp(-22/15, 27)
Error: Modular inverse does not exist
However, we can compute -22/15 modulo 26, since 15 and 26 are coprime:
>> -22/15 mod 26
2
Here are some examples where the modulus is a rational number. We have 23/3 = 9 * 4/5 + 7/15 = 10 * 4/5 - 1/3 and 23 = 28 * 4/5 + 3/5 = 29 * 4/5 - 1/5. Thus we obtain:
>> modp(23/3, 4/5), mods(23/3, 4/5), modp(23, 4/5), mods(23, 4/5)
7/15, -1/3, 3/5, -1/5
If one of the arguments is not a number, then a symbolic function call is returned:
>> delete x, m: x mod m, x mod 2, 2 mod m
x mod m, x mod 2, 2 mod m
modp
and mods
with non-numeric
arguments are printed in the operator notation:
>> modp(x, m), mods(x, m)
x mod m, x mod m
By default the binary operator mod
and the
equivalent function _mod
are both equivalent to
modp
. This can be changed by redefining
_mod
:
>> 11 mod 7, modp(11,7), mods(11,7)
4, 4, -3
>> _mod := mods: 11 mod 7; _mod := modp:
-3