Find the largest number that divides 245 and 1029 leaving remainder 5

Question

Find the largest number that divides 245 and 1029 leaving remainder 5 in each case.

Solution — Step by Step

If the largest number $d$ divides 245 leaving remainder 5, that means $d$ divides $(245 - 5) = 240$ exactly.

Similarly, $d$ divides $(1029 - 5) = 1024$ exactly.

So we need the largest number that divides both 240 and 1024 — which is their HCF.

240 = 2 \times 120 = 2 \times 2 \times 60 = 2^4 \times 15 = 2^4 \times 3 \times 5

So $240 = 2^4 \times 3 \times 5$ .

1024 = 2^{10}

(Since $2^{10} = 1024$ — a useful number to remember: $2^{10} = 1024 \approx 1000$ .)

HCF = product of common prime factors with lowest powers.

Common prime factor: only $2$ .

Lowest power of 2: $\min(4, 10) = 4$ .

\text{HCF}(240, 1024) = 2^4 = 16

Check: $245 \div 16 = 15$ remainder $5$ ✓ (since $15 \times 16 = 240$ , and $240 + 5 = 245$ )

Check: $1029 \div 16 = 64$ remainder $5$ ✓ (since $64 \times 16 = 1024$ , and $1024 + 5 = 1029$ )

The largest number is 16.

Why This Works

When a number $d$ divides $n$ leaving remainder $r$ , it means $n - r$ is perfectly divisible by $d$ . So $d$ is a factor of $(n - r)$ .

We subtract the remainder from each number to “clean up” the remainder, leaving values that are exact multiples of $d$ . The largest such $d$ is the HCF of those cleaned-up values.

This technique extends to three or more numbers — subtract the remainder from each and find HCF of all the results.

Alternative Method — Euclidean Algorithm

Instead of prime factorisation, we can find HCF(240, 1024) using repeated division (Euclid’s algorithm):

1024 = 4 \times 240 + 64

240 = 3 \times 64 + 48

64 = 1 \times 48 + 16

48 = 3 \times 16 + 0

When remainder = 0, the last non-zero remainder is the HCF. So HCF = 16. Same answer, different path.

For CBSE board exams, the Euclidean algorithm is faster when numbers are large. Prime factorisation is more transparent and easier to write up in a step-by-step solution for full marks.

Common Mistake

Many students forget to subtract the remainder before finding HCF. They directly compute HCF(245, 1029) = 7, which is wrong. Always subtract the given remainder first: HCF(245 − 5, 1029 − 5) = HCF(240, 1024) = 16.

Question

Solution — Step by Step

Why This Works

Alternative Method — Euclidean Algorithm

Common Mistake

Try These Next