How many integers between 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?
Find the smallest positive integer that leaves a remainder 5 when divided by 7, a remainder 6 when divided by 11, and a remainder 4 when divided by 13.
446 divided by 11
list multiples of 7 plus 1 past 200 :
204 211 218 225 232 239 246..
list multiples of 4 plus 3 past 200
203 207 211 215 219 223 227 231 235 239 AHHHH
239 is the smallest
this will happen again in 28 (multiply the 2 remainders)
so 239 267 295 323 ... 491
number of terms ??
consider it an arithmetic sequence where a = 239, d - 28 and n = ?
t(n) = a+(n-1)d
491 = 239 + (n-1)(28)
252 = 28n - 28
280 = 28n
n = 10
remainder of 5 when divided by 7 ---- 5 mod 7
remainder of 6 when divided by 11 --- 6 mod 11
remainder of 4 when divided by 13 --- 4 mod 13
we could do the same thing:
12 19 26 33 40 47 54 61 68 75 82 89 96 103 110 117 124 131 138 ...
6 17 28 39 50 61 72 83 94 105 116 127 138 149...
4 17 30 43 56 69 82 95 108 121 134 147...
mmmhh?
Let's try something completely different:
"The Chinese Remainder Theorem"
Google it to get several examples, there is a good Youtube
Z = 5 mod 7
Z = 6 mod 11
Z = 4 mod 13
X = 5b1 c1 + 6 b2 c2 + 4b3 c3
to get b's, multiply the mods
7x11x13 = 1001
b1 = 1001/7 = 143
b2 = 1001/11 = 91
b3 = 1001/13 = 77
sofar we have
X = 5(143) c1 + 6(91)c2 + 4(77)c3
now the tricky part
143(c1) = 1 mod 7
3c1 = 1 mod 7
3c1 = 8mod7
-4c1 = 8 mod 7
c1 = -2
91c2 = 1 mod 11
3c2 = 1mod11
3c2 = 12 mod 11
c2 = 4
77c3 = 1 mod 13
12 c3 = 1 mod 13
12c3 = -12 mod 13
c3 = -1
so X = 5(143)(-2) + 6(91)(4) + 4(77)(-1)
= 446 mod 1001
so the smallest such number is 446
check: 446/7 = 63 remainder 5
446/11 = 40 remainder 6
446/13 = 34 remainder 4
How about that, we could have gone for quite a bit using the simple method of just listing.
To find the number of integers between 200 and 500 that satisfy the given conditions, we can set up the following congruence equations:
x ≡ 1 (mod 7)
x ≡ 3 (mod 4)
We can solve this system of congruences using the Chinese Remainder Theorem.
Step 1: Find the solution to the congruence equation x ≡ 1 (mod 7).
To find a solution to this congruence, we can start by listing the numbers that satisfy this condition:
1, 8, 15, 22, ...
The sequence adds 7 each time. Therefore, the general form of the solution is:
x ≡ 7n + 1
Step 2: Find the solution to the congruence equation x ≡ 3 (mod 4).
To find a solution to this congruence, we can start by listing the numbers that satisfy this condition:
3, 7, 11, 15, 19, 23, ...
The sequence adds 4 each time. Therefore, the general form of the solution is:
x ≡ 4n + 3
Step 3: Set up the Chinese Remainder Theorem.
The Chinese Remainder Theorem states that if we have two congruences of the form:
x ≡ a (mod m)
x ≡ b (mod n)
where m and n are relatively prime, then the general form of the solution is:
x ≡ (a * n * y + b * m * z) (mod m * n)
In this case, m = 7 and n = 4.
Step 4: Solve the congruences using the Chinese Remainder Theorem.
Using the Chinese Remainder Theorem, we have:
x ≡ (1 * 4 * 1 + 3 * 7 * (-1)) (mod 7 * 4)
x ≡ (4 - 21) (mod 28)
x ≡ -17 (mod 28)
To find the smallest positive integer that satisfies this congruence, we can add a multiple of 28 to -17 until we get a positive number. By adding multiples of 28, we can find:
-17 + 28 = 11
-17 + 2 * 28 = 39
-17 + 3 * 28 = 67
Therefore, the smallest positive integer that satisfies the given conditions is 11.
To find the number of integers between 200 and 500 inclusive that satisfy the given conditions, we need to determine the number of integers that leave a remainder of 1 when divided by 7 and a remainder of 3 when divided by 4.
Step 1: Find the first integer that satisfies both conditions.
To find the first integer that leaves a remainder of 1 when divided by 7, we start with 200 and add 1 until we find a number that satisfies the condition. We find that 201 leaves a remainder of 1 when divided by 7.
To find the first integer that leaves a remainder of 3 when divided by 4, we start with 201 (the number we found in the previous step) and add 7 (the least common multiple of 7 and 4) until we find a number that satisfies the condition. We find that 205 leaves a remainder of 3 when divided by 4.
Step 2: Find the last integer that satisfies both conditions.
To find the last integer that leaves a remainder of 1 when divided by 7, we subtract 1 from 500 until we find a number that satisfies the condition. We find that 497 leaves a remainder of 1 when divided by 7.
To find the last integer that leaves a remainder of 3 when divided by 4, we subtract 7 from 497 (the number we found in the previous step) until we find a number that satisfies the condition. We find that 490 leaves a remainder of 3 when divided by 4.
Step 3: Calculate the number of integers between the first and last integers.
To calculate the number of integers between 205 and 490 inclusive, we subtract the first integer from the last integer and then add 1 (to include both the first and last integers in the count). Therefore, the number of integers between 200 and 500 inclusive that leave a remainder of 1 when divided by 7 and a remainder of 3 when divided by 4 is (490 - 205 + 1) = 286.
Therefore, there are 286 integers between 200 and 500 inclusive that leave a remainder of 1 when divided by 7 and a remainder of 3 when divided by 4.
---
To find the smallest positive integer that leaves a remainder of 5 when divided by 7, a remainder of 6 when divided by 11, and a remainder of 4 when divided by 13, we can use the Chinese Remainder Theorem (CRT).
Step 1: List out the given remainders and their respective divisors.
Remainder 5 when divided by 7: (5, 7)
Remainder 6 when divided by 11: (6, 11)
Remainder 4 when divided by 13: (4, 13)
Step 2: Calculate the product of all the divisors.
Product of divisors = 7 * 11 * 13 = 1001
Step 3: Calculate the individual remainders modulo their respective divisors.
Remainder 5 modulo 7 = 5
Remainder 6 modulo 11 = 6
Remainder 4 modulo 13 = 4
Step 4: Calculate the inverse modulo for each divisor.
Inverse modulo of 7 = 1001 / 7 = 143
Inverse modulo of 11 = 1001 / 11 = 91
Inverse modulo of 13 = 1001 / 13 = 77
Step 5: Calculate the sum of products of remainders, divisors, and inverse modulos.
Sum of (5 * 143 * 143^-1) + (6 * 91 * 91^-1) + (4 * 77 * 77^-1) = 30577
Step 6: Divide the final sum by the product of all the divisors.
Smallest positive integer = 30577 / 1001 = 30
Therefore, the smallest positive integer that leaves a remainder of 5 when divided by 7, a remainder of 6 when divided by 11, and a remainder of 4 when divided by 13 is 30.