Loading [MathJax]/jax/output/HTML-CSS/jax.js

First time here? Check out the FAQ!

Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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})
click to hide/show revision 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})
click to hide/show revision 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})