# Least-modulus description of congruences

Anonymous

Suppose I'm given a bunch of residues mod $n$. Is there an efficient/elegant way to get sage to calculate the least modulus $m$ and set of residues mod $m$ which describes the same set? For example if I give it "0,2,4,6 mod 8" it should simply return "0 mod 2".

edit retag close merge delete

Sort by ยป oldest newest most voted

If I've understood the question correctly, you are looking for the smallest (positive) divisor $m$ of $n$ such that if $S$ is your set of residues mod $n$, then $S+m=S$ (and also for the image of $S$ mod $m$).

So if $S=\lbrace mod(a_1,n),mod(a_2,n),\ldots,mod(a_d,n)\rbrace$ is a set of residues mod $n$ then this seems to do the trick:

def min_modulus(S):
## get n from data (could have entered it instead)
n=next(iter(S)).modulus()
## now loop
for m in divisors(n):
if S=={s+m for s in S}:
return m,{mod(s,m) for s in S}
## Won't ever get here because m=n will work.


An example run:

sage: S={mod(0,8),mod(2,8),mod(4,8),mod(6,8)}
sage: min_modulus(S)
(2, {0})

more

Hello,

I propose an improvement of the answer proposedby Kevin Buzzard as there is no need to factorize.

def min_modulus(residues, n):
# clean the input
n = ZZ(n)
residues = sorted(set(ZZ(r)%n for r in residues))

# find the list of number s so that:
#   residues + s = residues  modulo  n
r0 = residues[0]
S = []
for r in residues[1:]:
if all((rr+r-r0)%n in residues for rr in residues):
S.append(r-r0)

if not S:
return residues, n
else:
m = gcd(S)
return sorted(set(r%m for r in residues)), m


Then you got

sage: min_modulus([0,1,2,3,4,5,6,7], 8)
([0], 1)
sage: min_modulus([0,2,4,6,8], 8)
([0], 2)
sage: min_modulus([1,3,5,7], 8)
([1], 2)
sage: min_modulus([0,4], 8)
([0], 4)
sage: min_modulus([1,5], 8)
([1], 4)

more

If your set of residues were all of the integers modulo n where n was an extremely large and easy-to-factor number (like a power of two) then my method is much quicker than yours ;-)

( 2015-03-14 17:58:17 +0100 )edit

Actually, I do not think so :-) the test S == {s+m for s in S} contains a loop over all elements! And you do it for all divisors of n (but note that you can replace it with something like I did with an iterator and the all).

( 2015-03-14 21:03:14 +0100 )edit