Module 1 · RRB Station Master Mathematics

Number System

Updated 15 Nov 2026 · 3,876 words
Updated 21 Nov 2026
LCM, HCF, divisibility, remainders, unit digit.
LCM and HCF · divisibility rules · remainder theorem · unit digit · number of factors

Learning Objectives

  • Understand the fundamental concepts of Number System
  • Apply key formulas and techniques to solve problems
  • Practice with exam-level questions to build speed and accuracy

The Number System: Your Gateway to Mathematics

The number system is the bedrock of arithmetic, providing the language and rules necessary to understand everything from basic addition to complex algebraic problems. For candidates appearing in competitive exams, mastery of this topic is not optional; it is mandatory for securing a high score in the quantitative aptitude section. This lesson will systematically break down divisibility rules, the relationship between LCM and HCF, and essential simplification techniques that you must know by heart.

Divisibility Rules

A number is divisible by another if it can be divided without leaving a remainder. Instead of performing long division for every question, you should memorize these specific patterns which apply instantly to large numbers. The rule for 2 states that any number ending in an even digit (0, 2, 4, 6, 8) is divisible by 2. For 3 and 9, the trick involves summing all digits; if the sum is divisible by 3 or 9 respectively, so is the original number. The rule for 4 depends only on the last two digits of the number being divisible by 4. For 5, the number must end in 0 or 5. A number is divisible by 6 if it satisfies both rules for 2 and 3 simultaneously. For 8, check if the number formed by the last three digits is divisible by 8. The rule for 11 requires you to find the difference between the sum of digits at odd positions and even positions; if this difference is zero or a multiple of 11, the number is divisible.

LCM & HCF

The Highest Common Factor (HCF) is the largest number that divides two or more numbers exactly, while the Least Common Multiple (LCM) is the smallest number that is exactly divisible by two or more numbers. To find these, you must first understand prime factorization, which breaks a number down into its simplest building blocks (primes). The formula for HCF involves taking only the common prime factors of the given numbers and multiplying them together with their lowest powers. Conversely, to find the LCM, you take all the prime factors present in any of the numbers, multiplying them with their highest powers. A critical relationship connects these two concepts: for any two numbers, the product of the numbers is always equal to the product of their HCF and LCM. This means if you know three out of four values (Number 1, Number 2, HCF, or LCM), you can calculate the missing one.

Simplification

Simplification refers to reducing complex mathematical expressions into manageable parts before solving them. In competitive exams, questions often involve fractions mixed with decimals or large numbers that look intimidating at first glance. The strategy is to simplify the numerator and denominator separately before dividing. For example, if you have a fraction like 40/160, do not divide immediately; instead, notice that both are divisible by 40, reducing it instantly to 1/4. Similarly, when dealing with decimals, try to convert them into fractions or multiply the entire expression by powers of 10 to remove the decimal points entirely.

Solved Examples

Example 1: Finding HCF using Prime Factors
Find the HCF of 24, 36, and 60.

a) 6 b) 8 c) 12 d) 18
Solution: c) 12. First, we break each number down into its prime factors: 24 = 2 × 2 × 2 × 3; 36 = 2 × 2 × 3 × 3; and 60 = 2 × 2 × 3 × 5. To find the HCF, we look for the factors that appear in all three lists. The common factors are two 2s and one 3. Therefore, HCF = 2 × 2 × 3 = 12.
Example 2: Finding LCM using Prime Factors
Find the LCM of 12, 15, and 18.

a) 120 b) 150 c) 160 d) 180
Solution: d) 180. We start with prime factorization: 12 = 2² × 3¹; 15 = 2⁰ × 3¹ × 5¹; and 18 = 2¹ × 3². To find the LCM, we take the highest power of every prime number present. The highest power of 2 is 2² (from 12 or 18), the highest power of 3 is 3² (from 18), and the highest power of 5 is 5¹ (from 15). Multiplying these gives: 4 × 9 × 5 = 180.

Common Traps

Students often fall into specific traps that lead to incorrect answers during the exam. One major mistake is confusing the definitions of LCM and HCF; remember that HCF is always smaller than or equal to the smallest number in the set, while LCM is always greater than or equal to the largest number. Another common error is forgetting that 1 is a factor of every integer but is not a prime number. Students also frequently make calculation errors when applying the divisibility rule for 11 by adding digits incorrectly. Finally, many candidates ignore the relationship Product = LCM × HCF and try to solve problems from scratch rather than using this shortcut.

Memory Tricks

To retain these rules quickly, use these mnemonics and comparisons. For the cyclicity of unit digits in powers (like 2ⁿ or 7ⁿ), remember the cycle length is always 4 for most numbers; visualize a clock with 4 hours. For divisibility by 9, think "Nine" sounds like "New," implying you start fresh with the sum of digits. A helpful comparison for LCM and HCF is to think of HCF as the "Common Ground" (shared factors) and LCM as the "Meeting Point" where everyone arrives together (common multiple). When checking divisibility by 7, use the mnemonic "Double and Subtract": take the last digit, double it, and subtract from the rest.

Exam-Day Strategy
On exam day, do not spend more than 1-2 minutes on a number system question. If you get stuck on a divisibility rule, estimate the answer by checking the last digit or sum of digits to eliminate options immediately. Always verify your LCM and HCF answers using the product formula if time permits. Practice solving problems without a calculator to build speed and accuracy, as calculators are not allowed in competitive exams.

Remainder Theorem and Modular Arithmetic Applications

The remainder theorem states that for any integers a and b (with b > 0) there exist unique integers q (quotient) and r (remainder) such that a = bq + r and 0 ≤ r < b. In modular notation this is written as a ≡ r (mod b). The power of modular arithmetic lies in its compatibility with the basic operations: if a ≡ r₁ (mod m) and c ≡ r₂ (mod m) then a + c ≡ r₁ + r₂ (mod m), a − c ≡ r₁ − r₂ (mod m), and a × c ≡ r₁ × r₂ (mod m). Exponentiation follows the same rule, allowing large powers to be reduced by repeatedly applying the modulus. For a prime modulus p, Fermat’s little theorem gives a^(p−1) ≡ 1 (mod p) when a is not a multiple of p. Euler’s theorem generalises this to any modulus m using Euler’s totient function φ(m): a^φ(m) ≡ 1 (mod m) for coprime a and m. These results turn otherwise impossible calculations — such as the remainder of 2100 divided by 7 — into a few lines of work: φ(7)=6, 100 = 6×16 + 4, so 2100 ≡ (26)16 × 24 ≡ 116 × 16 ≡ 2 (mod 7). Modular arithmetic also underpins the solution of linear congruences, the Chinese Remainder Theorem, and many divisibility shortcuts used in competitive testing.

Cyclicity of Unit Digits in Powers

The unit digit of a positive integer raised to successive powers follows a repeating cycle. For bases ending in 0, 1, 5, or 6 the cycle length is 1 because the unit digit never changes. For bases ending in 4 or 9 the cycle length is 2 (4 → 6 → 4 … ; 9 → 1 → 9 …). For the remaining digits 2, 3, 7, and 8 the cycle length is 4. The complete cycles are: 2 → 4 → 8 → 6; 3 → 9 → 7 → 1; 7 → 9 → 3 → 1; 8 → 4 → 2 → 6. To find the unit digit of a^n, identify the unit digit of a, determine its cycle, compute n mod (cycle length), and pick the corresponding element (using the cycle length itself when the remainder is 0). For example, the unit digit of 72023: the cycle for 7 is length 4; 2023 mod 4 = 3, so the third element of the cycle (7 → 9 → 3 → 1) is 3. This technique eliminates the need for any large‑scale multiplication and is a staple of time‑bound arithmetic sections.

Worked Example: Unit Digit of a Large Power
Find the unit digit of 1247.
The unit digit of the base 12 is 2. The cycle for 2 is 2 → 4 → 8 → 6 (length 4). Compute 47 mod 4 = 3. The third element in the cycle is 8. Therefore the unit digit of 1247 is 8.
Exam‑Day Tip for Cyclicity
Memorise the four‑digit cycles for 2, 3, 7, 8 and the two‑digit cycles for 4, 9. When a question asks for the last digit of a huge exponent, write the base’s unit digit, its cycle length, and the exponent modulo that length. This three‑step routine takes under ten seconds and avoids any multiplication.

Properties of Consecutive Integers and Factorials

The product of any k consecutive integers is always divisible by k!. This follows because the binomial coefficient C(n, k) = n! / (k! (n−k)!) is an integer, and its numerator contains the product of k consecutive numbers. A direct consequence: among any three consecutive integers one is a multiple of 3, and at least one is even, so the product is a multiple of 6. For factorials, Legendre’s formula gives the exponent of a prime p in n! as Σ floor(n / p^i) for i = 1,2,… until p^i > n. This is the standard method to count trailing zeros in n! (use p=5). For instance, zeros in 100! = floor(100/5) + floor(100/25) = 20 + 4 = 24. Factorials also satisfy n! = n × (n−1)!, which is useful for simplifying expressions like (n+1)! / n! = n+1. In problems involving divisibility by a factorial, rewrite the given product as a binomial coefficient multiplied by the factorial to see the divisibility instantly.

Advanced LCM‑HCF Problems with Fractions and Decimals

The definitions of LCM and HCF extend naturally to rational numbers. For fractions in lowest terms, LCM( a/b , c/d ) = LCM(a, c) / HCF(b, d) and HCF( a/b , c/d ) = HCF(a, c) / LCM(b, d). The logic: a common multiple of the fractions must be an integer multiple of each, so its numerator must be a common multiple of the numerators while its denominator must divide both denominators — hence the denominator is the HCF of the denominators. Conversely, a common divisor of the fractions must divide each numerator and be a multiple of each denominator, giving the HCF of numerators over the LCM of denominators. For decimals, convert each to a fraction with a power‑of‑10 denominator, reduce to lowest terms, then apply the fraction formulas. Example: LCM of 0.6 and 0.15. Write 0.6 = 6/10 = 3/5, 0.15 = 15/100 = 3/20. LCM = LCM(3,3) / HCF(5,20) = 3 / 5 = 0.6. HCF = HCF(3,3) / LCM(5,20) = 3 / 20 = 0.15. These rules also solve “find the greatest number that divides 1.2, 2.4, and 3.6 leaving the same remainder” by converting to fractions and using HCF of the differences.

Chinese Remainder Theorem Basics for Competitive Exams

The Chinese Remainder Theorem (CRT) states that a system of simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ a_k (mod m_k) has a unique solution modulo M = m₁ m₂ … m_k provided the moduli are pairwise coprime. The constructive proof builds the solution as x = Σ a_i × M_i × y_i (mod M), where M_i = M / m_i and y_i is the modular inverse of M_i modulo m_i (i.e., M_i × y_i ≡ 1 (mod m_i)). For small moduli the inverse can be found by inspection or the extended Euclidean algorithm. Example: solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Here M = 105. M₁ = 35, inverse of 35 mod 3 is 2 (since 35×2=70≡1). M₂ = 21, inverse of 21 mod 5 is 1 (21≡1). M₃ = 15, inverse of 15 mod 7 is 1 (15≡1). Then x = 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105). The smallest positive solution is 23. CRT is invaluable for problems that ask for a number satisfying several remainder conditions, and it also underpins many cryptographic algorithms.

  • Assuming the cyclicity length is always 4; digits 0,1,5,6 have length 1 and 4,9 have length 2.
  • Forgetting to reduce the exponent modulo the cycle length and using the raw exponent instead.
  • Applying the fraction LCM/HCF formulas without first reducing fractions to lowest terms.
  • Treating decimal numbers as integers when computing LCM or HCF, ignoring the power‑of‑10 factor.
  • Using the Chinese Remainder Theorem when the moduli are not pairwise coprime; the theorem does not guarantee a solution in that case.
  • Neglecting negative remainders in modular arithmetic; always convert a negative remainder to its positive equivalent by adding the modulus.
  • Misapplying Legendre’s formula by stopping the summation too early or using the wrong prime for trailing‑zero problems.

Mastering these advanced techniques will significantly improve speed and accuracy in number system problems.

Euler's Totient Function and Its Applications in Modular Exponentiation

The Euler totient function φ(n) counts the positive integers not exceeding n that are coprime to n. For a prime power p^k the value is φ(p^k)=p^k−pk−1. Because φ is multiplicative for coprime arguments, φ(mn)=φ(m)φ(n) whenever gcd(m,n)=1. This allows rapid computation of φ for any integer once its prime factorisation is known. The central property for competitive examinations is Euler's theorem: if gcd(a,n)=1 then aφ(n)≡1 (mod n). Consequently, any exponent e can be reduced modulo φ(n) when the base a is coprime to the modulus n, i.e. a^e≡ae mod φ(n) (mod n). This reduction turns astronomically large powers into manageable calculations. For example, to find the remainder of 21000 upon division by 101, note that 101 is prime so φ(101)=100. Since gcd(2,101)=1, 21000≡21000 mod 100=20=1 (mod 101). When the base and modulus are not coprime, Euler's theorem cannot be applied directly; one must factor out the common divisor or use the Chinese Remainder Theorem on the prime‑power components. A frequent exam pattern asks for the last two digits of a huge power, which is equivalent to computing the power modulo 100. Because φ(100)=40, any base coprime to 100 can have its exponent reduced modulo 40. For bases sharing factors with 100 (e.g. 2, 5, 10) the problem is split into modulo 4 and modulo 25, solved separately, and recombined. Mastery of φ(n) computation and the exponent‑reduction rule is indispensable for time‑bound modular arithmetic questions.

Fermat's Little Theorem and Euler's Theorem for Composite Moduli

Fermat's little theorem is the special case of Euler's theorem when the modulus is prime: for prime p and integer a not divisible by p, ap−1≡1 (mod p). This yields an immediate primality test — if an−1≢1 (mod n) for some a coprime to n, then n is composite. However, the converse fails for Carmichael numbers (e.g. 561, 1105, 1729) which satisfy an−1≡1 (mod n) for every a coprime to n despite being composite. Euler's theorem extends the result to any modulus n: aφ(n)≡1 (mod n) provided gcd(a,n)=1. The exponent φ(n) is often much smaller than n−1, giving a sharper reduction. For instance, to evaluate 3200 (mod 100), φ(100)=40, so 3200≡3200 mod 40=30=1 (mod 100). When the base shares a factor with the modulus, write the modulus as a product of prime powers, apply Euler's theorem to each coprime component, and combine the residues via the Chinese Remainder Theorem. A typical twist in examinations is to ask for the remainder of a^b (mod m) where b itself is a huge expression such as a factorial or a tower of exponents. In such cases one first reduces the exponent modulo φ(m) (or modulo λ(m), the Carmichael function, which is the least universal exponent) after verifying coprimality. The Carmichael function λ(n) divides φ(n) and often yields a smaller cycle; for n=2^k with k≥3, λ(2^k)=2k−2 while φ(2^k)=2k−1. Knowing both φ and λ allows the most efficient exponent reduction and is a hallmark of high‑scoring candidates.

Technique: Reducing Exponents with Euler's Theorem
Find the remainder when 712345 is divided by 100.
Step 1: Check coprimality. gcd(7,100)=1, so Euler's theorem applies. Step 2: Compute φ(100). 100=22×52 ⇒ φ(100)=100×(1−1/2)×(1−1/5)=40. Step 3: Reduce the exponent modulo 40. 12345 mod 40 = 12345−40×308=12345−12320=25. Step 4: Compute 725 (mod 100). Use repeated squaring: 71=7; 72=49; 74=492=2401≡1 (mod 100). Since 74≡1, 725=74×6+1≡(74)6×7≡16×7≡7 (mod 100). The remainder is 7.
Exam‑Day Strategy
When a problem asks for a^b (mod m), first factor m and compute φ for each prime‑power factor. If gcd(a,m)=1, reduce b modulo φ(m) (or λ(m) if you know it). If gcd(a,m)≠1, split m into coprime parts, solve each part separately, then recombine with CRT. Write down the factorisation, φ values, and reduced exponent before any multiplication — this prevents arithmetic slips under time pressure.

Solving Linear Congruences with Non‑Coprime Moduli

A linear congruence ax≡b (mod m) has a solution if and only if d=gcd(a,m) divides b. When d>1 the congruence is equivalent to (a/d)x≡b/d (mod m/d), where the new coefficient a/d and modulus m/d are coprime. The unique solution modulo m/d can be found by multiplying both sides by the modular inverse of a/d modulo m/d, which exists because they are coprime. The full solution set modulo m consists of d distinct residues: x₀, x₀+m/d, x₀+2m/d, …, x₀+(d−1)m/d. For a system of two congruences x≡r₁ (mod m₁) and x≡r₂ (mod m₂) with non‑coprime moduli, a solution exists iff r₁≡r₂ (mod gcd(m₁,m₂)). When this condition holds, the system can be reduced to a single congruence modulo lcm(m₁,m₂) by the method of successive substitution or by constructing the solution using the extended Euclidean algorithm on the moduli. For example, solve 6x≡9 (mod 15). Here d=gcd(6,15)=3, and 3 divides 9, so solutions exist. Divide through: 2x≡3 (mod 5). The inverse of 2 modulo 5 is 3, giving x≡3×3≡9≡4 (mod 5). The three solutions modulo 15 are 4, 4+5=9, and 4+10=14. In competitive papers, such congruences often appear disguised as “find the smallest positive integer that leaves remainder 4 when divided by 6 and remainder 9 when divided by 15”. Translating to congruences and applying the gcd condition quickly reveals whether a solution exists and yields the answer without trial and error.

Advanced Simplification of Nested Radicals and Surd Expressions

Expressions of the form √(a±√b) can sometimes be denested into √x±√y with rational x,y. The necessary and sufficient condition is that a²−b is a perfect square, say c². Then √(a+√b)=√((a+c)/2)+√((a−c)/2) and √(a−√b)=√((a+c)/2)−√((a−c)/2), provided the inner radicands are non‑negative. For instance, √(7+√48): here a=7, b=48, a²−b=49−48=1=c². Then (a+c)/2=4, (a−c)/2=3, so √(7+√48)=√4+√3=2+√3. When the condition fails, the radical cannot be expressed as a sum of simpler square roots over the rationals. A related technique handles expressions like √(m)+√(n) squared: (√m+√n)²=m+n+2√(mn). Recognising this pattern allows rapid simplification of fractions containing surds in the denominator. Rationalising denominators of the form 1/(√a+√b) is done by multiplying numerator and denominator by √a−√b, yielding (√a−√b)/(a−b). For higher‑order roots, similar ideas apply using the identity (x−y)(xk−1+xk−2y+…+yk−1)=x^k−y^k. In examinations, nested radicals often appear in “simplify” questions where the answer is an integer or a simple surd. The quickest check is to square the candidate answer and compare with the original radicand. Memorising the denesting condition a²−b=c² and the resulting formulas saves valuable seconds.

Digital Root, Casting Out Nines, and Divisibility by 9 and 11

The digital root of a positive integer is obtained by repeatedly summing its digits until a single digit remains; equivalently, it is the remainder when the number is divided by 9, with the convention that a remainder of 0 corresponds to digital root 9. This property underlies the method of casting out nines, a quick sanity check for addition, subtraction, and multiplication: compute the digital root of each operand, perform the same operation on the digital roots, and compare with the digital root of the result. A mismatch signals an arithmetic error. For divisibility by 9, a number is divisible by 9 exactly when its digit sum (and hence its digital root) is a multiple of 9. For divisibility by 11, the alternating sum of digits (sum of digits in odd positions minus sum of digits in even positions) determines the remainder modulo 11; the number is a multiple of 11 iff this alternating sum is a multiple of 11. These rules extend to checking large products: the digital root of a product equals the digital root of the product of the digital roots. In competitive exams, casting out nines is frequently used to eliminate wrong options in multiple‑choice questions without full computation. For example, to verify whether 12345×6789 equals 83810205, compute digital roots: 12345→6, 6789→3, product digital root→6×3=18→9. The candidate 83810205 has digit sum 8+3+8+1+0+2+0+5=27→9, so it passes the test. A failure would immediately discard the option. The alternating‑sum rule for 11 is similarly powerful for spotting multiples of 11 in long numbers. Combining both checks gives a two‑layer filter that catches the majority of computational slips.

  • Assuming Euler's theorem applies when the base and modulus are not coprime.
  • Using φ(m) for exponent reduction without checking that the reduced exponent is non‑negative (remember a0≡1).
  • Forgetting that a linear congruence ax≡b (mod m) has solutions only when gcd(a,m) divides b.
  • Attempting to denest √(a±√b) without verifying that a²−b is a perfect square.
  • Misapplying the alternating‑sum rule for 11 by starting the sign from the wrong end (the rule works from either end but the parity of the number of digits matters).
  • Neglecting to reduce fractions to lowest terms before applying LCM/HCF formulas for rational numbers.
  • Overlooking the Carmichael function λ(n) when φ(n) gives a larger exponent cycle, leading to unnecessary computation.

These advanced techniques complete the toolkit needed for the most challenging number system questions.

Practice Questions

Percentage →