Revision history [back]

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)