A number when divided by 361 gives a remainder 47. If the Same number ...
Let the number be = 361 + 47 = 408
When we divide 408 by 19 we get remainder 9.
View all questions of this test
A number when divided by 361 gives a remainder 47. If the Same number ...
Given information:
- Number gives a remainder of 47 when divided by 361
- Number is divided by 19
To find: Remainder when the number is divided by 19
Approach:
- Use the Chinese Remainder Theorem to find the number
- Divide the number by 19 to find the remainder
Chinese Remainder Theorem:
Let n1, n2, ..., nk be positive integers which are pairwise coprime.
For any given sequence of integers a1, a2, ..., ak, there exists an integer x solving the following system of simultaneous congruences:
x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ ak mod nk
Using the Chinese Remainder Theorem, we can find the number as follows:
Step 1: Find a number x that satisfies the first congruence:
x ≡ 47 mod 361
Step 2: Find a number y that satisfies the second congruence:
y ≡ x mod 19
Step 3: Find the remainder when y is divided by 19
Solution:
Step 1:
Let x = 47 + 361k where k is an integer
x ≡ 47 mod 361
Step 2:
y = x = 47 + 361k
y ≡ x mod 19
y ≡ 47 + 361k mod 19
y ≡ 9k + 14 mod 19
Step 3:
To find the remainder when y is divided by 19, we need to find the smallest non-negative integer that is of the form 9k + 14.
Starting with k = 0, we get:
9k + 14 = 14
which is not divisible by 19. Trying k = 1, we get:
9k + 14 = 23
which gives a remainder of 4 when divided by 19. Trying k = 2, we get:
9k + 14 = 32
which gives a remainder of 14 when divided by 19. Trying k = 3, we get:
9k + 14 = 41
which gives a remainder of 3 when divided by 19. Trying k = 4, we get:
9k + 14 = 50
which gives a remainder of 12 when divided by 19. Trying k = 5, we get:
9k + 14 = 59
which gives a remainder of 1 when divided by 19. Trying k = 6, we get:
9k + 14 = 68
which gives a remainder of 10 when divided by 19. Trying k = 7, we get:
9k + 14 = 77
which gives a remainder of 18 when divided by 19. Trying k = 8, we get:
9k + 14 = 86
which gives a remainder of 7 when divided by 19. Trying k = 9, we get:
9k + 14 = 95
which gives a remainder of 16 when divided by 19. Trying k = 10, we get:
9k + 14 = 104
which gives a remainder of 5 when divided by 19. Trying k = 11, we get:
9k + 14 = 113
which