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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

Problem 531

Post by 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.
Image
User avatar
RobertStanforth
Administrator
Posts: 1459
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 531

Post by RobertStanforth »

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

Post by KING-OLE »

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

Re: Problem 531

Post by 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.
"
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: Problem 531

Post by nicolas.patrois »

a=x mod n means a−x=0 mod n ie n divides a-x.
Image
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 531

Post by 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.
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 531

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

Re: Problem 531

Post by 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...)
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: Problem 531

Post by nicolas.patrois »

Or a%n = x%n if % is the remainder of the euclidean division.
Image
CT075
Posts: 1
Joined: Thu Dec 03, 2015 2:21 pm

Re: Problem 531

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

Re: Problem 531

Post by 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.
Post Reply