Thread: Little number theory based maths problem

Hi!

I have chosen a positive integer. On division by 14 my integer gives remainder 6. On division by 15 my integer gives remainder 2. On division by 13 my integer gives remainder 12. What is the smallest possible positive integer I could have chosen?

Good luck!

Go through my method in this post.

Edit: Unless you meant this as a challenge problem of course, in which case this thread is under the wrong sub-forum.

Thanks alexmahone.... i can follow that to a point, but then in your example, you are given an equation whereby the remainder is 0, so then you are able make the equation where d=0 and get your answer.... i am not given this, so how do i get around it?

Originally Posted by sirellwood

Thanks alexmahone.... i can follow that to a point, but then in your example, you are given an equation whereby the remainder is 0, so then you are able make the equation where d=0 and get your answer.... i am not given this, so how do i get around it?

How about posting some working?

Originally Posted by alexmahone

How about posting some working?

x = 6(mod14)
x=14a +6

x=2(mod15)
14a+6 = 2(mod15)
14a=-4(mod15)
14a=11(mod15)
14a=15b+11

combining my equations.... x=15b+17

15b+17=12(mod13)
15b=-5(mod13)
3b=-1(mod13)
3b=13c-1

x=15b+17
x=5(13c-1)+17
x=65c+12

.....from here i am stuck, i seem to be going roundin circles?

Originally Posted by sirellwood

combining my equations.... x=15b+17

This merely implies that x=2 (mod 15). But you already knew that! Which means that you haven't used the previous part of the problem.

14a=-4 (mod 15)
7a=-2 (mod 15)
a=4 (mod 15)
a=15b+4

x=14a+6=14(15b+4)+6=210b+62

Can you proceed?

210b+62 = 12mod13
210b=-50mod13
21b=-5mod13
b=-25mod13
b=1mod13
b=13c+1

x=210(13c+1)+62
x=2730c +272

now i know at this point, we are meant to imply that c=0 and infer that x=272.... But i dont fully understand why we can say clearly c=0?

Originally Posted by sirellwood

But i dont fully understand why we can say clearly c=0?

Because the problem asks for the smallest possible positive integer.

oh ok, thank you, basically i was confused as to why it was only at this point that we put c=0, rather than say take b=0 in x= 210b+62.... Then i realised that because at that point, not all parts of the question had been considered, i.e. x=12(mod13) hadnt been processed.... this makes sense now :-)

oinw