Find the smallest positive integer x such that:
x mod 2 = 1
x mod 3 = 2 and
x mod 5 = 3
_______
What is the next integer with this property?
______
[You will have to do some trial and error, but thinking about divisiblity should lead you to some patterns.]
x mod 2 = 1
x mod 3 = 2 and
x mod 5 = 3
_______
What is the next integer with this property?
______
[You will have to do some trial and error, but thinking about divisiblity should lead you to some patterns.]
-
From the first congruence we know x =2p+1 for some integer p.
Substituting this into the second congruence gives us:
2p+1 = 2 (mod 3)
2p = 1 (mod 3)
p = 1/2 (mod 3)
= 2 (mod 3)
Thus p = 3q+2 for some integer q. Substitute this back into the first congruence to find:
x = 2(3q+2)+1 = 6q+5
Now substitute this last into the final congruence
6q+5 = 3 (mod 5)
6q = 3 (mod 5)
q = 1/2 (mod 5)
= 3 (mod 5)
Thus q= 5r+3 for some integer r. Substituting this back into x = 6q+5 gives us
x = 6(5r+3)+5
= 30r + 23
This tell us that any integer congruent to 23 modulo 30 solves the system:
23, 53, 83, ...
Substituting this into the second congruence gives us:
2p+1 = 2 (mod 3)
2p = 1 (mod 3)
p = 1/2 (mod 3)
= 2 (mod 3)
Thus p = 3q+2 for some integer q. Substitute this back into the first congruence to find:
x = 2(3q+2)+1 = 6q+5
Now substitute this last into the final congruence
6q+5 = 3 (mod 5)
6q = 3 (mod 5)
q = 1/2 (mod 5)
= 3 (mod 5)
Thus q= 5r+3 for some integer r. Substituting this back into x = 6q+5 gives us
x = 6(5r+3)+5
= 30r + 23
This tell us that any integer congruent to 23 modulo 30 solves the system:
23, 53, 83, ...
-
If you thought about it, the smallest multiple of 5 plus 3 is 5*1 + 3 = 8, the next smallest is 5*2 + 3 = 13, followed by 5*3 + 3 = 18, 5*4 + 3 = 23
23 (mod 2) = 1 (mod 2)
23 (mod 3) = 2 (mod 3)
23 (mod 5) = 3 (mod 5)
23 (mod 2) = 1 (mod 2)
23 (mod 3) = 2 (mod 3)
23 (mod 5) = 3 (mod 5)