find the greatest number which is divide by 742 and 1162 leaving 7 as a remainder.
The Correct Answer and Explanation is:
To find the greatest number which divides 742 and 1162 leaving a remainder of 7, follow these steps:
Step-by-Step Solution
Let the required greatest number be N.
Since dividing 742 and 1162 by N leaves a remainder of 7, we can express the condition mathematically:
- 742 ≡ 7 (mod N) → (742 − 7) is divisible by N
- 1162 ≡ 7 (mod N) → (1162 − 7) is divisible by N
So,
- 742 − 7 = 735
- 1162 − 7 = 1155
This means N divides both 735 and 1155 exactly. Therefore, N must be the greatest common divisor (GCD) of 735 and 1155.
Let’s find the GCD of 735 and 1155 using the Euclidean algorithm:
- Divide 1155 by 735: 1155 ÷ 735 = 1, remainder = 420
→ 1155 = 1×735 + 420 - Divide 735 by 420: 735 ÷ 420 = 1, remainder = 315
→ 735 = 1×420 + 315 - Divide 420 by 315: 420 ÷ 315 = 1, remainder = 105
→ 420 = 1×315 + 105 - Divide 315 by 105: 315 ÷ 105 = 3, remainder = 0
→ 315 = 3×105
So, GCD(735, 1155) = 105
Thus, the greatest number N that divides both 742 and 1162 leaving a remainder of 7 is:
Answer: 105
Explanation
This problem is a classic example of using modular arithmetic and the Euclidean algorithm to find the greatest common divisor under certain conditions. We are told that a number divides two other numbers leaving the same remainder. In this case, both 742 and 1162 leave a remainder of 7 when divided by some unknown number N.
The key idea is that if a number N divides both 742 and 1162 with the same remainder, then N must divide the difference between each of those numbers and the remainder. That is, N must divide both 742 − 7 and 1162 − 7. This leads to the numbers 735 and 1155.
Once we simplify the problem to finding a number that divides both 735 and 1155 exactly, it becomes a straightforward GCD problem. We apply the Euclidean algorithm, which is an efficient method to find the greatest common divisor of two integers. We do this by repeatedly subtracting the smaller number from the larger one or dividing and taking the remainder until we reach zero. The last non-zero remainder is the GCD.
In this case, the GCD of 735 and 1155 is 105. Therefore, 105 is the greatest number that divides both 742 and 1162 leaving a remainder of 7. To verify, 742 divided by 105 gives a quotient of 7 and a remainder of 7. Similarly, 1162 divided by 105 gives a quotient of 11 and a remainder of 7.
Hence, the correct answer is 105.
