Ask Your Question
0

Least-modulus description of congruences

asked 2015-03-12 18:38:52 -0500

anonymous user

Anonymous

updated 2015-03-14 03:52:27 -0500

Suppose I'm given a bunch of residues mod $n$. Is there an efficient/elegant way to get sage to calculate the least modulus $m$ and set of residues mod $m$ which describes the same set? For example if I give it "0,2,4,6 mod 8" it should simply return "0 mod 2".

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2015-03-14 03:51:52 -0500

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)
edit flag offensive delete link more

Comments

If your set of residues were all of the integers modulo n where n was an extremely large and easy-to-factor number (like a power of two) then my method is much quicker than yours ;-)

Kevin Buzzard gravatar imageKevin Buzzard ( 2015-03-14 11:58:17 -0500 )edit

Actually, I do not think so :-) the test S == {s+m for s in S} contains a loop over all elements! And you do it for all divisors of n (but note that you can replace it with something like I did with an iterator and the all).

vdelecroix gravatar imagevdelecroix ( 2015-03-14 15:03:14 -0500 )edit
1

answered 2015-03-13 19:47:52 -0500

Kevin Buzzard gravatar image

updated 2015-03-14 11:55:03 -0500

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})
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-03-12 18:38:52 -0500

Seen: 56 times

Last updated: Mar 14 '15