# Revision history [back]

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 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)
s=S.pop()
n=s.modulus()
##
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})


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)
s=S.pop()
n=s.modulus()
##
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})


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)
s=S.pop()
n=s.modulus()
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})