calendarBack
Quant

/

Numbers

/

Factors & Remainders
ALL MODULES

CAT 2025 Lesson : Factors & Remainders - HCF with Remainders

bookmarked

3. Remainders

When a number, say nn, is divided by a divisor (d)(d), it leaves a quotient (q)(q) and a remainder (r)(r). So, nn can be expressed as n\bm{n} = dq\bm{dq} + r\bm{r}

For example, when 3737 (n)(n) is divided by 99 (d)(d), we get a quotient of 44 (q)(q) and remainder of 11 (r)(r).

37=9×4+137 = 9 \times 4 + 1

Remainders are typically expressed as a non–negative value less than the divisor. ∴ 0≤r<d\bm{0 \leq r \lt d}

3.1 Adding/Subtracting Divisors

Property: If a multiple of the divisor is added to or subtracted from the number, the remainder does not change.

Let Kd\bm{Kd}, be the multiple of the divisor that is added to the number, n\bm{n}.

Rem(n+Kdd)=Rem(dq+r+Kdd)=Rem(d(q+k)d)+Rem(rd)\mathrm{Rem} \left(\dfrac{n + Kd}{d}\right) = \mathrm{Rem} \left(\dfrac{dq + r + Kd}{d}\right) = \mathrm{Rem} \left(\dfrac{d( q + k)}{d}\right) + \mathrm{Rem} \left(\dfrac{r}{d}\right)

[As dd(qq +K+ K) is perfectly divisible by dd, it's remainder is 00.]

=0+r=r= 0 + r = r

3.2 HCF concept with Remainders

HCF is applied in the following two types of questions on remainders.

Type 1: Finding the largest divisor that divides xx, yy and zz to leave remainders aa, bb and cc respectively.

When the numbers are subtracted from their respective remainders, they are perfectly divisible by the divisor.

∴ Largest Divisor == HCF[(xx - aa), (yy - bb), (zz - cc)]

Example 11

When each of 100100, 125125, 150150 and 200200 is divided by a natural number nn, the remainders are 44, 55, 66 and 88 respectively. What is the largest possible value of nn?

Solution

100100 when divided by nn leaves a remainder of 44.
This means n\bm{n} perfectly divides 100−4=96100 - 4 = \bm{96}.

∴n\bm{n} perfectly divides (100−4100 - 4), (125−5125 - 5), (150−6150 - 6) and (200−8200 - 8) =96= \bm{96}, 120\bm{120}, 144\bm{144} and 192\bm{192}.

Largest number that can divide a set of numbers is it's HCF.
HCF(96,120,144,19296, 120, 144, 192) =24= \bm{24}

Answer: 2424

Example 12

When each of 5757, 8484 and 102102 is divided by xx, the remainder is 33. What is the maximum possible value of xx?

Solution

xx perfectly divides (57−357 - 3), (84−384 - 3), (102−3102 - 3) =54,81,99= 54, 81, 99

Largest value of x=x = HCF (5454, 8181, 9999) =9= 9

Alternatively

As the remainders are equal, the divisor should be a factor of the difference between numbers.

Difference between numbers == (84−5784 - 57), (102−84102 - 84) =27,18= 27, 18
HCF(2727, 1818) =9= 9

Answer: 99

Type 2: Finding the largest divisor that divides xx, yy and zz to leave the same unknown remainder

As explained in the second solution of Example 1212 above, when the remainders are the same, then the largest possible divisor is the HCF of the difference between numbers.

Where x>y>zx \gt y \gt z,
Largest Divisor == HCF[(x−yx - y), (y−zy - z)]

Example 13

What is the largest positive integer that divides 8888, 3939, 102102 , and 6060, and leaves the same remainder?

Solution

Difference of numbers = (60−3960 - 39), (88−6088 - 60), (102−88102 - 88) =21,28,14= 21, 28, 14

HCF(2121, 2828, 1414) =7= 7

Answer: 77

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now arrow-right
videovideo-lock