# Little number theory based maths problem

Printable View

• May 2nd 2011, 06:53 AM
sirellwood
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!
• May 2nd 2011, 07:08 AM
alexmahone
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.
• May 2nd 2011, 07:26 AM
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?
• May 2nd 2011, 07:33 AM
alexmahone
Quote:

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?
• May 2nd 2011, 07:40 AM
sirellwood
Quote:

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?
• May 2nd 2011, 07:53 AM
alexmahone
Quote:

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?
• May 2nd 2011, 08:35 AM
sirellwood
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?
• May 2nd 2011, 08:42 AM
alexmahone
Quote:

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.
• May 2nd 2011, 08:48 AM
sirellwood
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 :-)
• May 4th 2011, 11:18 AM
hmmm
oinw