Problem 531
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 531
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.
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
 Administrator
 Posts: 1459
 Joined: Mon Dec 30, 2013 11:25 pm
Re: Problem 531
Interpret it instead as x%4=2 and x%6=4.

 Posts: 9
 Joined: Sat Sep 17, 2011 11:03 pm
Re: Problem 531
Current text
"
Let g(a,n,b,m) be the smallest nonnegative 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 nonnegative 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.
"
"
Let g(a,n,b,m) be the smallest nonnegative 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 nonnegative 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
 Posts: 118
 Joined: Fri Jul 26, 2013 4:54 pm
 Contact:
Re: Problem 531
a=x mod n means a−x=0 mod n ie n divides ax.
Re: Problem 531
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 (ax) 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.
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 (ax) 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.
_{Jaap's Puzzle Page}
Re: Problem 531
Hm, the problem asks for the smallest nonnegative 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 ?
So why should we talk about the behaviour of the %operator for negative numbers in various computer languages at all ?

 Posts: 9
 Joined: Sat Sep 17, 2011 11:03 pm
Re: Problem 531
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...)
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
 Posts: 118
 Joined: Fri Jul 26, 2013 4:54 pm
 Contact:
Re: Problem 531
Or a%n = x%n if % is the remainder of the euclidean division.
Re: Problem 531
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?
[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?
Re: Problem 531
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.