## Problem 531

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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 post any spoilers
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

### 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.
RobertStanforth
Posts: 1459
Joined: Mon Dec 30, 2013 11:25 pm

### Re: Problem 531

Interpret it instead as x%4=2 and x%6=4.
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

### Re: Problem 531

Thanks - that helps.
meconopsis
Posts: 9
Joined: Sat Sep 17, 2011 11:03 pm

### Re: Problem 531

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
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 a-x.
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### 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 (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
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 531

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
Posts: 9
Joined: Sat Sep 17, 2011 11:03 pm

### Re: Problem 531

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.
CT075
Posts: 1
Joined: Thu Dec 03, 2015 2:21 pm

### 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?
idantlol
Posts: 16
Joined: Mon Jul 11, 2011 1:14 pm

### 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.