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):
    """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})

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):
    """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})

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):
    """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})