Question

Ok. Another question.

Answer 1

How many positive integers N from 1 to 5000 satisfy both congruences, \[N\equiv 5\pmod{12} and N\equiv 11\pmod{13}? \]

Answer 2

So there's 417 which satisfy the first, and 384, I think, which satisfy the second. Now count the ones which satisfy both. You can do that using the technique in the solution of one of your previous problems!

http://openstudy.com/study#/updates/52194835e4b06211a67cad34

Answer 3

Is the answer 60?

Answer 4

Ooops, I actually misread the question and thought it said or... Come to think of it, I think I did that for one of the previous ones too (the one which we left halfway).

But I don't think it's 60.

Answer 5

chinese remainder theorem might help for this

should not be too hard since \(13-12=1\)

Answer 6

Is it 89?

Answer 7

We've been using it for the past couple of problems.Suppose you want to solve
\[N \equiv a \mod m_1, N\equiv b \mod m_2,\]where \(m_1\) and \(m_2\) are coprime. Then the Chinese remainder theorem says that a solution \(N\) exists, and that all solutions \(N\) are congruent modulo \(m_1m_2\).

Answer 8

It's smaller than 89...

Answer 9

Here's why the theorem is useful... it means we only need to find one solution \(N\), and we know all of them!

And finding a single solution isn't terribly hard. You have
\(N≡5 + 12m, N≡11 + 13n\)
for some integers \(m,n\). So set them equal...
\(5 + 12m = 11 + 13n\)
and if you can find a single pair of values \(m,n\) which satisfy that, then you have all your solutions!

Answer 10

just to butt in, since
\[13-12=1\] the first one to work is
\[13\times 11-12\times 5=83\]
you can check that this solves both
then add \(12\times 13=156\) repeatedly to get them all

Answer 11

usually it is somewhat harder, and often you have more congruences to solve, but for this one you can get the 1 right off the bat

Answer 12

wait...what?

Answer 13

Ooh I get what you are saying Erin! Just solve for m and n.

Answer 14

@satellite73 I think 83 solves
\[N=11 \mod 12, N =5\mod 13\]not the original equations... ;)

Answer 15

ugh. now I'm confused. do you already know what the answer is erin?

Answer 16

I believe it's 32.

Answer 17

but...why?

Answer 18

oh crap, did i get that backwards?

Answer 19

32 is right.

Answer 20

but the 8 answers i submitted before that aren't XD

Answer 21

Did you find a value of \(m\) and \(n\)?

Answer 22

7 and 6?

Answer 23

i screwed up didn't i?
should be
\[13\times 5-2\times 11=-67\]

Answer 24

@orple8 They seem to work. I just used -6 and -6. Not that it matters much - you just need a single pair of values. So now that you have m and n, you have a solution N.

Answer 25

Oh! right!

Answer 26

@satellite73 Assuming that's 12*13, that looks much better :)

Answer 27

Um, 12*11, I mean. Now I'm screwing up...

Answer 28

Thanks! Erin you are magical. I swear. Either that or you are genius.

Answer 29

I've got to go to sleep. My head is throbbing so badly...

Math for 3 hours straight is no good for you.

Answer 30

@orple8 Neither. I'm still trying to get my head around satellite's stuff!

What are you talking about? 3 hours of maths is excellent for you :P Or have my maths lecturers been lying to me all this time...

Answer 31

so not good for my head. maybe good for my intellectual level. *clutches head and makes pitiful mewing noises until Erin agrees.* lol

Answer 32

well, I'm going to sleep now. bye!