# 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

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
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)
(, 1)
sage: min_modulus([0,2,4,6,8], 8)
(, 2)
sage: min_modulus([1,3,5,7], 8)
(, 2)
sage: min_modulus([0,4], 8)
(, 4)
sage: min_modulus([1,5], 8)
(, 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 ;-)

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). 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