Least-modulus description of congruences

edit

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)

    # return the answer
    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)

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