calendarBack
Quant

/

Numbers

/

Factors & Remainders
ALL MODULES

CAT 2025 Lesson : Factors & Remainders - Concepts & Cheatsheet

bookmarked
Note: The video for this module contains a summary of all the concepts covered in the Factors & Remainders lesson. The video would serve as a good revision. Please watch this video in intervals of a few weeks so that you do not forget the concepts. Below is a cheatsheet that includes all the formulae but not necessarily the concepts covered in the video.

   8. Cheatsheet

11) When two or more numbers are prime factorised, HCF is the product of primes with the least powers across the numbers and LCM is the product of primes with the highest powers across the numbers. LCM ≥\geq HCF

22) For 22 numbers aa and bb, a×ba \times b = HCF(aa , bb) ×\times LCM (aa, bb)

33) HCF of fractions = HCF of numeratorsLCM of denominators\dfrac{\mathrm{HCF \ of \ numerators}}{\mathrm{LCM \ of \ denominators}} and LCM of fractions = LCM of numeratorsHCF of denominators\dfrac{\mathrm{LCM \ of \ numerators}}{\mathrm{HCF \ of \ denominators}}

44) Any number represented in the form ap×bq×cr×.....a^p \times b^q \times c^r \times ....., where aa, bb, cc, .. are prime numbers has (pp + 11) (qq + 11) (rr + 11) ... factors.

4.14.1) For 2p×bq×cr×.....2^p \times b^q \times c^r \times ..... , where bb, cc, ... are odd prime numbers, odd number of factors = (qq + 11)(rr + 11) ... .

4.24.2) Total Factors −- Odd Factors = Even Factors

55) If a number x\bm{x} has n\bm{n} factors, then x can be expressed as a product of two natural numbers in n2\dfrac{n}{2} ways if nn is even and (n+1)2\dfrac{(n + 1)}{2} ways if nn is odd.

66) If a number x\bm{x} has has n\bm{n} factors, then the product of its factors is x(n2)x^{\left(\frac{n}{2}\right)}.

77) HCF Concepts
(a) The largest number that divides xx, yy and zz to leave remainders aa, bb and cc = HCF[(xx - aa), (yy - bb), (zz - cc)]

(b) The largest number that divides xx, yy and zz to leave the same remainder = HCF[(xx - yy), (yy - zz)]

88) LCM Concepts
(a) Numbers leaving the same remainder (rr) for a given set of divisors = k\bm{k} ×\times LCM of divisors + r\bm{r}

(b) Numbers leaving the same difference (dd) in remainders and divisors = k\bm{k} ×\times LCM of divisors - d\bm{d}

(c) For all other cases, we express numbers in dqdq + rr format and find the smallest possible solution, say xx. These numbers are of the form k\bm{k} ×\times LCM of divisors + x\bm{x}

99) Successive Division: Once we find the smallest number (say xx) that satisfies, other numbers are of the form k\bm{k} ×\times Product of divisors + x\bm{x}

1010) Remainder rules
Rem(nd)=Rem(a1+a2+a3+......d) \mathrm{Rem} \left(\dfrac{n}{d}\right) = \mathrm{Rem} \left(\dfrac{a_1 + a_2 + a_3 +......}{d}\right)

=Rem(a1d)+Rem(a2d)+Rem(a3d)+..... \mathrm{Rem} \left(\dfrac{a_1}{d}\right) + \mathrm{Rem} \left(\dfrac{a_2}{d}\right) + \mathrm{Rem} \left(\dfrac{a_3}{d}\right) + .....

Rem(nd)=Rem(a1×a2×a3×......d) \mathrm{Rem} \left(\dfrac{n}{d}\right) = \mathrm{Rem} \left(\dfrac{a_1 \times a_2 \times a_3 \times......}{d}\right)

= Rem(a1d)×Rem(a2d)×Rem(a3d)×.....\mathrm{Rem} \left(\dfrac{a_1}{d}\right) \times \mathrm{Rem} \left(\dfrac{a_2}{d}\right) \times \mathrm{Rem} \left(\dfrac{a_3}{d}\right) \times .....

Rem((dq+r)nd)=Rem(rnd)\mathrm{Rem} \left(\dfrac{(dq + r)^n}{d}\right) = \mathrm{Rem} \left(\dfrac{r^n}{d}\right)

1111) Euler's Totient of n[ϕ(n)]n [\phi(n)] is the number of co-prime positive integers less than nn.
If the prime factors of nn are x1,x2,x3,....x_1, x_2, x_3, ....,
ϕ(n)\bm{ \phi (n)} = n×(1−1x1)×(1−1x2)×(1−1x3)×..... n \times \left(1 - \dfrac{1}{x_1}\right) \times \left(1 - \dfrac{1}{x_2}\right) \times \left(1 - \dfrac{1}{x_3}\right) \times .....

1212) Fermat's Theorem: If nn and dd are co-prime integers, then Rem(nϕ(d)d)=1 \mathrm{Rem} \left(\dfrac{n^{\phi(d)}}{d}\right) = 1

1313) Chinese Remainder: Where n and d are not co-prime, the remainders for each of the prime factors (raised to their respective powers) is found. These are then used to find the common remainder.

1414) Number of ways in which a number nn can be expressed as the difference of squares of positive integers is x2\dfrac{x}{2} if xx is even and (x−1)2\dfrac{(x - 1)}{2} if xx is odd, where

(a) xx is the number of factors of nn if n\bm{n} is odd; and
(b) xx is the number of factors of n4\dfrac{n}{4} if n\bm{n} is divisible by 4.

1515) Number of ways in which xx can be expressed as the sum of consecutive natural numbers is the number of odd factors of xx other than 11.

1616) Where kk is a constant, the remainder when a polynomial f(x)f(x) is divided by (xx - kk), is f(k)f(k).

1717) Wilson's Theorem: Where nn is a prime number, Rem((n−2)!n)=1\mathrm{Rem} \left(\dfrac{(n - 2)!}{n}\right) = 1 and Rem((n−1)!n)=n−1\mathrm{Rem} \left(\dfrac{(n - 1)!}{n}\right) = n - 1 .

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now arrow-right
videovideo-lock