Weight of a modular Diophantine inequality
Definition
Let \(a,b\) be positive integers such that \(0 < a < b\) and let \(ax ~ (mod ~ b) \le x\) be the modular Diophantine inequality. It is defined the weight of the modular Diophantine inequality, denoted by \(w(a,b)\), as \(w(a,b) = b - gcd(a, b) - gcd(a-1, b)\).
Examples
\(\circ\) Let \(a = 15, b = 24\) and the modular Diophantine inequality \(15x ~ (mod ~ 24)\). We have, \(gcd(15, 24) = 3\) and \(gcd(14, 24) = 2\). Then, the weight is
\[ w(a,b) = b - gcd(a,b) - gcd(a-1, b) = 24 - 3 - 2 = 19. \]
Examples with GAP
Nowadays, there are no functions in package NumericalSgps related to weight of a modular Diophantine inequality. However, given two positive integers \(a,b\), the following function returns the weight of the modular Diophantine inequality \(a'x ~ (mod ~ b) \le x\), where \(a' = a ~ (mod ~ b)\).
gap> WeightModDiophantineIneq := function(a,b)
> local c;
> if not IsInt(a) then
> Error("First argument must be a positive integer");
> fi;
> if a <= 0 then
> Error("First argument must be a positive integer");
> fi;
> if not IsInt(b) then
> Error("First argument must be a positive integer");
> fi;
> if b <= 0 then
> Error("First argument must be a positive integer");
> fi;
> c := a mod b;
> return b - Gcd(c,b) - Gcd(c-1,b);
> end;
function( a, b ) ... end\(\diamond\) Let \(a = 12, b = 27\) and the modular Diophantine inequality \(ax ~ (mod ~ b) \le x\). If we use the function defined above,
gap> WeightModDiophantineIneq(12, 27);
23Then, the weight of the modular Diophantine inequality \(12x ~ (mod ~ 27) \le x\) is \(w(12,27) = 23\).
References
https://gap-packages.github.io/ numericalsgps.