Problem 531

[KING-OLE]

Maybe I'm not quite awake yet, but I don't understand the question.

In the example, a system of x=2%4 and x=4%6 gives the result 10.

Is the meaning of "mod" in this question something else?

This has been out for just over 8 hours, and 74 people have already solved it, so I think I'm missing something here.

Thanks for any comments that may clarify this for me.

[RobertStanforth]

Interpret it instead as x%4=2 and x%6=4.

[KING-OLE]

Thanks - that helps.

[meconopsis]

Current text
"
Let g(a,n,b,m) be the smallest non-negative solution x to the system:
x = a mod n
x = b mod m
if such a solution exists, otherwise 0.

E.g. g(2,4,4,6)=10, but g(3,4,4,6)=0.
"
seems wrong. IMO it should read
"
Let g(a,n,b,m) be the smallest non-negative solution x to the system:
a = x mod n
b = x mod m
if such a solution exists, otherwise 0.

E.g. g(2,4,4,6)=10, but g(3,4,4,6)=0.
"

[nicolas.patrois]

a=x mod n means a−x=0 mod n ie n divides a-x.

[jaap]

mod in this context is not an operator. It is not the same thing as the % operator.
The equation should really have used the ≡ symbol, meaning "is congruent to", instead of =. See for example Problem 123 (View Problem).

The modular equation x≡a modulo n means that x and a have the same residues modulo n, i.e. the same remainder after a division by n. Formally that is defined as Nicolas says as (a-x) is divisible by n. If a and x are positive you could also think of it in terms of the % operator as x%n = a%n.

Note however that the % operator is not always defined in the same way for negative numbers in various computer languages. Problem 531 uses positive numbers only, so it is not an issue here. For example, some languages give (-11)%3 = -2 and 10%3 = 1, so even though -11 is congruent to 10 modulo 3, (-11)%3 and 10%3 differ.

[hk]

Hm, the problem asks for the smallest non-negative number that is a solution to the system described.
So why should we talk about the behaviour of the %-operator for negative numbers in various computer languages at all ?

[meconopsis]

Ah. I had been reading it as
a = ( x mod n )
rather than
( a = x ) mod n.
All is now clear. (Not that it makes solving the problem any easier...)

[nicolas.patrois]

Or a%n = x%n if % is the remainder of the euclidean division.

[CT075]

I'm really frustrated at this point; I've checked my work several times and can't spot the error. Can someone check these numbers for me?

[SNIPPED]
for x <= n < m < y:
100,1000:
1000, 2000:
10000, 15000:
1000000, 1002000:

E: Excuse me, did not notice that posting potentially wrong results is also disallowed. Results removed, but can someone please PM me the values for those bounds?

[idantlol]

Probably a bit too late to help CT075, but my guess is that the error was in the case where n and m are not coprime.