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={mod(a1,n),mod(a2,n),…,mod(ad,n)} is a set of residues mod n then this seems to do the trick:
def min_modulus(S):
"""Proposed solution to http://ask.sagemath.org/question/26173 ."""
## get n from data (could have entered it instead)
s=S.pop()
n=s.modulus()
S.add(s)
##
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})
![]() | 2 | No.2 Revision |
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={mod(a1,n),mod(a2,n),…,mod(ad,n)} is a set of residues mod n then this seems to do the trick:
def min_modulus(S):
"""Proposed solution to http://ask.sagemath.org/question/26173 ."""
## get n from data (could have entered it instead)
s=S.pop()
n=s.modulus()
S.add(s)
##
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})
![]() | 3 | No.3 Revision |
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={mod(a1,n),mod(a2,n),…,mod(ad,n)} is a set of residues mod n then this seems to do the trick:
def min_modulus(S):
"""Proposed solution to http://ask.sagemath.org/question/26173 ."""
## get n from data (could have entered it instead)
s=S.pop()
n=s.modulus()
S.add(s)
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})