# Homework Help: Linear congruence

1. Oct 21, 2008

### Norway

1. The problem statement, all variables and given/known data
Basically:
Olivia pays 234 kr for a train ticket, and John pays 264 kr for the same kind of ticket. After half a year, Olivia has paid 54 kr more than John. How many tickets did they buy each?

By the way, kr is the currency in Norway.

2. Relevant equations
Uhm, I guess:
ax + ny = b <=> ax is congruent with b (mod n)
and all the usual equations for congruences.

3. The attempt at a solution
This is what I've done (I agree with the solution [which I have] quite far, but there's one bit I don't understand):
234x = 264y + 54
234x is congruent with 54 (mod 264) => gcd(234, 264) = 6 => 6|54

39x is congruent with 9 (mod 44)

(9 + 44n)/39 has to be a natural number. n = 6

39x is congruent with 9 + 44 * 6 (mod 44)
39x is congruent with 273 (mod 44)
x is congruent with 7 (mod 44)

x = 7 + 44n

Okay, the solution agrees with me this far. Then I got blank, as this is supposed to have 6 incongruences modulo 264, so I checked it up in the solution. It says: "If Olivia takes the train every weekend, x_(max) = 24 => x = 7 + 44 * 0 = 7" and then finds y = 6.

But I didn't understand that about xmax being 24, and why it apparently doesn't matter at all that it's 24. Why does it tell me to continue like that? I understand everything that's done, except from that tiny part about deciding that n=0 is the only possible solution for x = 7 + 44n.

Thanks :)

2. Oct 22, 2008

### HallsofIvy

Where did the information "Olivia takes the train every weekend" come from? Was that stated in the problem? Is it impossible that Olivia could take the train everyday? It looks to me like they are saying that if Olivia took took the train NO MORE than every weekend, she could not have taken more than 52/2= 26 (but that's not 24!) train trips in half a year. Since with n positive x= 7+ 44nz> 50 which is larger than 24 (or 26). Is it impossible that Olivia took the train 51 times? Is there no other information?

Last edited by a moderator: Oct 22, 2008
3. Oct 22, 2008

### Norway

I think I got it now anyways, but you're right. This is the task as it's written (although bad grammar, prehaps, because of my not-so-good translation):
Olivia and John lives in a bedsit (according to a dictionary, although I've never heard of it before), and sometimes take the train home during weekends. Olivia pays 234 for a round trip ticket, and John pays 264 kr for the same kind of ticket. In the course of half a year, Olivia paid 54 kr more than John for the travels by train. How many times did each of them travel home by train this half year?

As I said, the key answers agreed with me all the way to x = 7 + 44n, and then it said:
"If Olivia travels home every weekend, then x_(max) = 24"
They probably thought 4 weeks * 6 months = 24 weeks.
But then it's just a right arrow towards the next equation: x = 7 + 44*0 = 7. Which is the correct answer, but what was the deal of mentioning 24 or x_max at all? I can't see where it has been useful.

Although, my guess is that it tells us that x must be between 0 and 26, which leaves us with x = 7 as the only possible solution (because we had 6 originally, right? seeing as 6 was the greatest common divisor of 234 and 264?) which again leaves us with y = 6

x = 7, y = 6

Kinda talking to myself here, but I'm trying to convince myself that I might have had full control of this one.

4. Oct 23, 2008

### HallsofIvy

Ah, it is that "sometimes take the train home during weekends." that puts the limit on how many times they may use the train. There are no more than 26 weekends in half a year. A "bedsit", I believe, is British for a "bed-sitting room": a small apartment consisting of a single bedroom, "sitting room" (living room), and, of course, bathroom and kitchen.

5. Oct 23, 2008

### Norway

Yes, "bedsit" was a translation of the Norwegian word "hybel", which is a small apartment you live in when you study in other cities, for example. Well, thanks :)