This came up as sub-problem during Young-Han’s group meeting today and we mulled over it for a few minutes but didn’t come up with a non-ugly answer. I’m sure, given the number of Real Mathematicians ™ who read this, that someone out there knows of an “obvious” explanation.

Suppose I give you *p* integers in an arbitrary order (where *p* is prime). While maintaining the order and using only addition, multiplication, and parenthesis, is it always possible to make an expression which evaluates to 0 mod *p*?

I think it’s true, but I’m sure there’s some special property of that I have forgotten. I guess further generalizations would include whether or not it’s possible for arbitrary (not necessarily prime), how many elements of an arbitrary field you would need, and so on. I’d ask this on MathOverflow but… meh. It’s probably a homework problem.

### Like this:

Like Loading...

*Related*

Not only is it true, but I don’t think p has to be prime.

If you an find a set of consecutive elements that add to 0 mod p, you can add that, put it in parentheses, and multiply it by everything else. We’ll show such a set always exists.

Consider the sums:

a_1

a_1+a_2

a_1+a_2+a_3

…

a_1+a_2+…+a_p

If these p sums are all different mod p, one of them must be 0 mod p. If they’re not all different, take any two that are the same, and their difference is a sum of consecutive integers equal to 0 mod p. Either way, we’re done.

(Now why can’t I answer questions related to my research this quickly?)

Also, p is necessary as well as sufficient (since a sequence of (p-1) 1’s is no good).

Would (1-1).(1+1+…+1) be acceptable when we have(p-1) 1’s?

Subtraction is not allowed…

Yes, I just noticed that subtraction is not allowed: sorry about that. But if p is not a prime, say p = 6, then

(1+1).(1+1+1)

is 0 mod 6, and so (p-1) 1’s might still massaged into 0 mod p.

Well that certainly is simpler than the algorithmic road we were treading down…

Pingback: Solving Puzzles « Information Ashvins

Pingback: Solving Puzzles « Information Ashvins