Study guide
2.3 HCF and LCM Properties, Prime Factorization & Practical Word Problems
RRB Section Controller 2026: Free Written CBT Study Guide Exam
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Exam Overview & Operational Profile
1.1 Written CBT Pattern, Scoring & Selection 1.2 Eligibility, Documents & A-2 Medical Requirements
2 Chapter 2: Number Systems & Arithmetic Foundations
2.1 Number Systems, Divisibility Rules, Prime Factorization & Remainder Theorem 2.2 Unit Digits, Cyclicity Rules & Power Modulo Calculations 2.3 HCF and LCM Properties, Prime Factorization & Practical Word Problems 2.4 Fractions, Decimals, Surds, Indices & BODMAS Simplification
3 Chapter 3: Commercial Arithmetic: Percentages, Profit & Rates
3.1 Percentages, Fractional Equivalents, Successive Variations & Population Formulas 3.2 Cost Price, Selling Price, Profit/Loss Percentage, Dishonest Dealer & Discount Schemes 3.3 Simple Interest, Compound Interest Formulas, Annual/Semi-Annual Compounding & Difference Traps
4 Chapter 4: Ratios, Proportions, Mixtures & Partnerships
4.1 Ratios, Duplicate/Sub-Duplicate Ratios, Direct and Inverse Variations & Proportional Sharing 4.2 Averages, Change in Average, Batsman/Bowling Averages & Replacement Problems 4.3 Rule of Alligation, Removal-Replacement Mixtures & Partnership Capital-Time Sharing
5 Chapter 5: Motion Dynamics, Time, Distance & Train Logistics
5.1 Time, Speed, Distance Relations, Average Speed & Unit Conversions 5.2 Train Problems: Passing Poles, Platforms, Moving Objects & Relative Speed in Opposite/Same Directions 5.3 Upstream, Downstream Boat Velocity, Still Water Speed & Circular Track Races
6 Chapter 6: Work Efficiency, Pipes & Operational Scheduling
6.1 Individual and Group Work, Efficiency Ratios, Work Equivalences & Mandays Formula 6.2 Alternate Day Working, Negative Work & Wage Distribution Based on Work Done 6.3 Inlet and Outlet Pipes, Net Filling Rate, Alternating Flow & Tank Leakage Problems
7 Chapter 7: Algebra, Linear Equations & Progressions
7.1 Algebraic Identities, Polynomial Factorization & Systems of Linear Equations in Two Variables 7.2 Quadratic Equations, Nature of Roots, Discriminant Analysis & Maximum/Minimum Values 7.3 Arithmetic Progressions (AP), General Term, Sum of n Terms & Sequence Modeling
8 Chapter 8: Mensuration: 2D Areas & 3D Solids
8.1 Lines, Angles, Triangle Theorems, Congruence/Similarity & Circle Tangent Properties 8.2 Perimeter and Area of Quadrilaterals, Polygons, Circles & Shaded Region Problems 8.3 Surface Area and Volume of Cubes, Cuboids, Cylinders, Cones, Spheres & Melting-Recasting Solids
9 Chapter 9: Statistics, Probability & Data Interpretation
9.1 Mean, Median, Mode, Range, Mean Deviation & Standard Deviation 9.2 Permutations, Combinations, Classical Probability, Independent Events & Odds 9.3 Tabular Data Interpretation, Bar Charts, Grouped Graphs & Percentage Calculation Shortcuts 9.4 Pie Charts (Angle vs Percentage), Line Trend Graphs & Quantitative Data Sufficiency
10 Chapter 10: Multi-Source & Graphical Analysis
10.1 Multi-Source Analysis, Set Data & Arrangement 10.2 Scatter Plots, Histograms & Distribution Curves
11 Chapter 11: Deductive Logic, Statements & Binary Puzzles
11.1 Syllogisms, Sets & Possibility Conclusions 11.2 Critical Reasoning: Implicit Assumptions, Strong vs Weak Arguments & Course of Action 11.3 Binary Logic: Truth-Tellers, Liars, Alternators & Matrix Logic Deductions
12 Chapter 12: Relational, Directional, Clock & Calendar Reasoning
12.1 Direct Family Relations, Coded Blood Relations & Family Tree Tree-Mapping Methods 12.2 Cardinal & Ordinal Directions, Multi-Step Turn Paths, Pythagorean Distance & Shadow Timing 12.3 Clock Hands Angular Speed, Angle Between Hands at Given Time, Coincidence & Faulty Clocks 12.4 Odd Days Concept, Reference Date Calculations, Leap Year Rules & Repeating Calendar Years
13 Chapter 13: English Reading Comprehension
13.1 English Comprehension: Main Idea, Support & Inference 13.2 English Comprehension: Application, Structure & Style
14 Chapter 14: Mental Reasoning: Analogies & Series
14.1 Semantic, Letter & Number Analogies 14.2 Number Series: Differences, Powers & Missing Terms 14.3 Interleaved, Recursive & Wrong-Term Series
15 Chapter 15: Mental Reasoning: Coding & Ranking
15.1 Letter Shifts, Reversal & Numerical Codes 15.2 Message Intersections & Conditional Coding Tables 15.3 Ranking, People Between & Position Interchanges
16 Chapter 16: Mental Reasoning: Seating Arrangements
16.1 Linear Seating & Parallel Rows 16.2 Circular Seating, Facing & Rotational Symmetry
2.3 HCF and LCM Properties, Prime Factorization & Practical Word Problems
Key Takeaways Explain This Topic AI
Highest Common Factor (HCF/GCD) takes the minimum prime power across numbers, while Least Common Multiple (LCM) takes the maximum prime power.
The identity LCM ( a , b ) HCF ( a , b ) = a b \text{LCM}(a,b)\text{HCF}(a,b)=ab LCM ( a , b ) HCF ( a , b ) = ab holds for two positive integers; it is not a general identity for three or more.
For fractions in irreducible form: HCF = HCF of numerators LCM of denominators \text{HCF} = \frac{\text{HCF of numerators}}{\text{LCM of denominators}} HCF = LCM of denominators HCF of numerators and LCM = LCM of numerators HCF of denominators \text{LCM} = \frac{\text{LCM of numerators}}{\text{HCF of denominators}} LCM = HCF of denominators LCM of numerators .
For fictional events repeating at fixed commensurable intervals, LCM gives the first common recurrence; real railway signal operation is not a periodic-alarm model.
Remainder classification distinguishes HCF difference models (greatest divisor of ∣ x − y ∣ , ∣ y − z ∣ , ∣ z − x ∣ |x-y|, |y-z|, |z-x| ∣ x − y ∣ , ∣ y − z ∣ , ∣ z − x ∣ ) from LCM models with constant additive ( k ⋅ LCM + r k \cdot \text{LCM} + r k ⋅ LCM + r ) or subtractive ( k ⋅ LCM − d k \cdot \text{LCM} - d k ⋅ LCM − d ) offsets.
Last updated: October 2026
- Definitions and Fundamental Methods
- Highest Common Factor (HCF) / Greatest Common Divisor (GCD)
The HCF of two or more positive integers is the largest positive integer that divides each of the numbers without leaving a remainder.
Least Common Multiple (LCM)
The LCM of two or more positive integers is the smallest positive integer that is divisible by each of the given numbers. +-----------------------------------------------------------------------------+
- | COMPUTATIONAL METHODS COMPARISON |
- +-----------------------------------------------------------------------------+
- | 1. PRIME FACTORIZATION METHOD |
- | Write each number in canonical prime powers: |
- | A = p_1^(a_1) * p_2^(a_2) * ... |
- | B = p_1^(b_1) * p_2^(b_2) * ... |
- | HCF = Product of MINIMUM powers: Prod p_i^min(a_i, b_i) |
- | LCM = Product of MAXIMUM powers: Prod p_i^max(a_i, b_i) |
- +-----------------------------------------------------------------------------+
- | 2. EUCLID'S DIVISION ALGORITHM (FOR HCF) |
- | Based on the identity: gcd(A, B) = gcd(B, A mod B) |
- | Divide larger by smaller until remainder is 0. Last non-zero divisor is |
- | the exact HCF. Highly efficient for large, multi-digit numbers. |
- +-----------------------------------------------------------------------------+
- Fundamental Product Rules & Multi-Variable Relations
- The Two-Number Product Theorem
For any two positive integers a a a and b b b : HCF ( a , b ) × LCM ( a , b ) = a × b \text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b HCF ( a , b ) × LCM ( a , b ) = a × b
Warning
The Three-Number Fallacy: The identity HCF ( a , b , c ) × LCM ( a , b , c ) = a × b × c \text{HCF}(a, b, c) \times \text{LCM}(a, b, c) = a \times b \times c HCF ( a , b , c ) × LCM ( a , b , c ) = a × b × c is FALSE . For example, consider 4 , 6 , 8 4, 6, 8 4 , 6 , 8 : HCF ( 4 , 6 , 8 ) = 2 \text{HCF}(4, 6, 8) = 2 HCF ( 4 , 6 , 8 ) = 2 and LCM ( 4 , 6 , 8 ) = 24 \text{LCM}(4, 6, 8) = 24 LCM ( 4 , 6 , 8 ) = 24 . Their product is 2 × 24 = 48 2 \times 24 = 48 2 × 24 = 48 , whereas 4 × 6 × 8 = 192 ≠ 48 4 \times 6 \times 8 = 192 \neq 48 4 × 6 × 8 = 192 = 48 .
For three positive integers a , b , c a, b, c a , b , c , the mathematically rigorous identity is: LCM ( a , b , c ) = a ⋅ b ⋅ c ⋅ HCF ( a , b , c ) HCF ( a , b ) ⋅ HCF ( b , c ) ⋅ HCF ( c , a ) \text{LCM}(a, b, c) = \frac{a \cdot b \cdot c \cdot \text{HCF}(a, b, c)}{\text{HCF}(a, b) \cdot \text{HCF}(b, c) \cdot \text{HCF}(c, a)} LCM ( a , b , c ) = HCF ( a , b ) ⋅ HCF ( b , c ) ⋅ HCF ( c , a ) a ⋅ b ⋅ c ⋅ HCF ( a , b , c )
- HCF and LCM of Fractions, Decimals & Powers
- Fractions
Before applying formulas, all fractions must be reduced to their simplest irreducible form p q \frac{p}{q} q p where gcd ( p , q ) = 1 \gcd(p, q) = 1 g cd ( p , q ) = 1 : HCF ( a b , c d , e f ) = HCF ( a , c , e ) LCM ( b , d , f ) \text{HCF}\left(\frac{a}{b}, \frac{c}{d}, \frac{e}{f}\right) = \frac{\text{HCF}(a, c, e)}{\text{LCM}(b, d, f)} HCF ( b a , d c , f e ) = LCM ( b , d , f ) HCF ( a , c , e ) LCM ( a b , c d , e f ) = LCM ( a , c , e ) HCF ( b , d , f ) \text{LCM}\left(\frac{a}{b}, \frac{c}{d}, \frac{e}{f}\right) = \frac{\text{LCM}(a, c, e)}{\text{HCF}(b, d, f)} LCM ( b a , d c , f e ) = HCF ( b , d , f ) LCM ( a , c , e )
Decimals
To compute the HCF or LCM of decimal numbers:
Count the maximum number of decimal places across all terms (say, k k k places).
Multiply every number by 10 k 10^k 1 0 k to convert them into integers.
Compute the HCF or LCM of the resulting integers.
Divide the final result by 10 k 10^k 1 0 k .
Exponential Powers with Common Bases
For powers of the same integer base x > 1 x>1 x > 1 (using the rational-fraction convention for negative exponents):
Positive exponents: HCF ( x p , x q , x r ) = x min ( p , q , r ) \text{HCF}(x^p, x^q, x^r) = x^{\min(p, q, r)} HCF ( x p , x q , x r ) = x m i n ( p , q , r ) and LCM ( x p , x q , x r ) = x max ( p , q , r ) \text{LCM}(x^p, x^q, x^r) = x^{\max(p, q, r)} LCM ( x p , x q , x r ) = x m a x ( p , q , r ) .
Negative exponents: HCF ( x − 2 , x − 5 , x − 8 ) = x − 8 \text{HCF}(x^{-2}, x^{-5}, x^{-8}) = x^{-8} HCF ( x − 2 , x − 5 , x − 8 ) = x − 8 (smallest value) and LCM ( x − 2 , x − 5 , x − 8 ) = x − 2 \text{LCM}(x^{-2}, x^{-5}, x^{-8}) = x^{-2} LCM ( x − 2 , x − 5 , x − 8 ) = x − 2 (largest value).
- Operational Railway & Aptitude Word Problem Models
- Model 1: Synchronized Fictional Indicators
In a fictional timing exercise, independent indicator lamps flash at fixed intervals of t 1 , t 2 , t 3 , … t_1, t_2, t_3, \dots t 1 , t 2 , t 3 , … seconds. This is a periodic-event model, not a description of railway signalling.
The events occur simultaneously at time intervals equal to LCM ( t 1 , t 2 , t 3 , … ) \text{LCM}(t_1, t_2, t_3, \dots) LCM ( t 1 , t 2 , t 3 , … ) .
If the events start simultaneously at t = 0 t = 0 t = 0 , the number of simultaneous occurrences within a total elapsed time T T T is: Total Simultaneous Occurrences = ⌊ T LCM ⌋ + 1 \text{Total Simultaneous Occurrences} = \left\lfloor \frac{T}{\text{LCM}} \right\rfloor + 1 Total Simultaneous Occurrences = ⌊ LCM T ⌋ + 1
- (If the question asks how many times they toll after the start, do not add 1.)
- Model 2: Circular Track Rendezvous
Two or more locomotives or athletes circulate around a closed circular loop of length L L L with constant speeds v 1 , v 2 , v 3 v_1, v_2, v_3 v 1 , v 2 , v 3 .
Time taken by each to complete one full revolution: T 1 = L v 1 , T 2 = L v 2 , T 3 = L v 3 T_1 = \frac{L}{v_1}, T_2 = \frac{L}{v_2}, T_3 = \frac{L}{v_3} T 1 = v 1 L , T 2 = v 2 L , T 3 = v 3 L .
Rendezvous at Starting Point: They will all meet simultaneously at the starting point after a time equal to: T start = LCM ( T 1 , T 2 , T 3 ) T_{\text{start}} = \text{LCM}(T_1, T_2, T_3) T start = LCM ( T 1 , T 2 , T 3 )
Rendezvous Anywhere on Track (Two Bodies): They meet anywhere on the loop at intervals of L ∣ v 1 − v 2 ∣ \frac{L}{|v_1 - v_2|} ∣ v 1 − v 2 ∣ L (same direction, unequal speeds) or L v 1 + v 2 \frac{L}{v_1 + v_2} v 1 + v 2 L (opposite direction).
For the fractional HCF/LCM convention, use positive rational quantities: a common divisor divides each quantity by an integer, and a common multiple is an integer multiple of each. Circular return formulas assume simultaneous departure and commensurable lap times.
Remainder Classification Models
Remainder problems in HCF and LCM fall into distinct mathematical patterns that frequently appear on the CBT: +-----------------------------------------------------------------------------+
- | REMAINDER MODELS TAXONOMY |
- +-----------------------------------------------------------------------------+
- | HCF REMAINDER MODELS (Finding the GREATEST DIVISOR) |
- | |
- | Case 1: Leaves same known remainder r when dividing x, y, z |
- | Required Number = HCF(x - r, y - r, z - r) |
- | |
- | Case 2: Leaves same UNKNOWN remainder when dividing x, y, z |
- | Required Number = HCF(|x - y|, |y - z|, |z - x|) |
- | |
- | Case 3: Leaves different remainders a, b, c when dividing x, y, z |
- | Required Number = HCF(x - a, y - b, z - c) |
- +-----------------------------------------------------------------------------+
- | LCM REMAINDER MODELS (Finding the SMALLEST DIVIDEND) |
- | |
- | Case 1: Leaves same remainder r when divided by x, y, z |
- | Required Number = k * LCM(x, y, z) + r |
- | |
- | Case 2: Leaves different remainders a, b, c such that: |
- | (x - a) = (y - b) = (z - c) = d (Constant Difference) |
- | Required Number = k * LCM(x, y, z) - d |
- +-----------------------------------------------------------------------------+
For greatest-divisor problems, verify that the proposed divisor exceeds every required remainder. Otherwise no such divisor exists. For LCM-offset models, choose an integer k k k giving a positive dividend and valid remainders. If no lower bound on the dividend is imposed, k = 0 k=0 k = 0 can be valid in the common-positive-remainder model; do not automatically select k = 1 k=1 k = 1 .
- Worked Examples
- Worked Example 1: Periodic Indicator Synchronization
Problem: Four fictional indicator lamps flash every 24 seconds, 36 seconds, 54 seconds, and 72 seconds respectively. If all four lamps flash simultaneously at exactly 08:00:00 AM, how many times will they flash simultaneously between 08:00:00 AM and 09:12:00 AM (inclusive of both endpoints)?
Step 1: Compute the LCM of the signal intervals: Express each interval in canonical prime factor form: 24 = 2 3 × 3 1 24 = 2^3 \times 3^1 24 = 2 3 × 3 1 36 = 2 2 × 3 2 36 = 2^2 \times 3^2 36 = 2 2 × 3 2 54 = 2 1 × 3 3 54 = 2^1 \times 3^3 54 = 2 1 × 3 3 72 = 2 3 × 3 2 72 = 2^3 \times 3^2 72 = 2 3 × 3 2 LCM = 2 max ( 3 , 2 , 1 , 3 ) × 3 max ( 1 , 2 , 3 , 2 ) = 2 3 × 3 3 = 8 × 27 = 216 seconds \text{LCM} = 2^{\max(3, 2, 1, 3)} \times 3^{\max(1, 2, 3, 2)} = 2^3 \times 3^3 = 8 \times 27 = 216 \text{ seconds} LCM = 2 m a x ( 3 , 2 , 1 , 3 ) × 3 m a x ( 1 , 2 , 3 , 2 ) = 2 3 × 3 3 = 8 × 27 = 216 seconds
The lamps synchronize every 216 seconds ( 3 minutes and 36 seconds 3 \text{ minutes and } 36 \text{ seconds} 3 minutes and 36 seconds ).
Step 2: Determine total elapsed duration in seconds: From 08:00:00 AM to 09:12:00 AM is 1 hour and 12 minutes = 72 minutes = 72 \text{ minutes} = 72 minutes . T = 72 × 60 = 4 , 320 seconds T = 72 \times 60 = 4,320 \text{ seconds} T = 72 × 60 = 4 , 320 seconds
Step 3: Compute simultaneous occurrences: T LCM = 4320 216 = 20 \frac{T}{\text{LCM}} = \frac{4320}{216} = 20 LCM T = 216 4320 = 20
Since both endpoints (including the start at 08:00:00 AM) are included: Total Changes = 20 + 1 = 21 \text{Total Changes} = 20 + 1 = 21 Total Changes = 20 + 1 = 21
Conclusion: The lamps flash simultaneously 21 times .
Worked Example 2: LCM Model with Constant Difference
Problem: Find the least number of wagons in a freight rake inventory such that when partitioned into sidings containing 12, 16, 18, or 21 wagons each, there remain 7, 11, 13, and 16 wagons unaccommodated respectively.
Step 1: Check for a constant difference between divisor and remainder: 12 − 7 = 5 12 - 7 = 5 12 − 7 = 5 16 − 11 = 5 16 - 11 = 5 16 − 11 = 5 18 − 13 = 5 18 - 13 = 5 18 − 13 = 5 21 − 16 = 5 21 - 16 = 5 21 − 16 = 5
A constant difference exists: d = 5 d = 5 d = 5 .
Step 2: Compute LCM ( 12 , 16 , 18 , 21 ) \text{LCM}(12, 16, 18, 21) LCM ( 12 , 16 , 18 , 21 ) : 12 = 2 2 × 3 12 = 2^2 \times 3 12 = 2 2 × 3 16 = 2 4 16 = 2^4 16 = 2 4 18 = 2 × 3 2 18 = 2 \times 3^2 18 = 2 × 3 2 21 = 3 × 7 21 = 3 \times 7 21 = 3 × 7 LCM = 2 4 × 3 2 × 7 = 16 × 9 × 7 = 144 × 7 = 1 , 008 \text{LCM} = 2^4 \times 3^2 \times 7 = 16 \times 9 \times 7 = 144 \times 7 = 1,008 LCM = 2 4 × 3 2 × 7 = 16 × 9 × 7 = 144 × 7 = 1 , 008
Step 3: Apply the constant difference formula: N = LCM − d = 1 , 008 − 5 = 1 , 003 N = \text{LCM} - d = 1,008 - 5 = 1,003 N = LCM − d = 1 , 008 − 5 = 1 , 003
Step 4: Verification: 1003 ÷ 12 = 83 with remainder 7 ( 12 × 83 = 996 ) 1003 \div 12 = 83 \text{ with remainder } 7 \quad (12 \times 83 = 996) 1003 ÷ 12 = 83 with remainder 7 ( 12 × 83 = 996 ) 1003 ÷ 16 = 62 with remainder 11 ( 16 × 62 = 992 ) 1003 \div 16 = 62 \text{ with remainder } 11 \quad (16 \times 62 = 992) 1003 ÷ 16 = 62 with remainder 11 ( 16 × 62 = 992 ) 1003 ÷ 18 = 55 with remainder 13 ( 18 × 55 = 990 ) 1003 \div 18 = 55 \text{ with remainder } 13 \quad (18 \times 55 = 990) 1003 ÷ 18 = 55 with remainder 13 ( 18 × 55 = 990 ) 1003 ÷ 21 = 47 with remainder 16 ( 21 × 47 = 987 ) 1003 \div 21 = 47 \text{ with remainder } 16 \quad (21 \times 47 = 987) 1003 ÷ 21 = 47 with remainder 16 ( 21 × 47 = 987 )
Conclusion: The least number of wagons is 1,003 .
Worked Example 3: HCF Unknown Same Remainder Model
Problem: Find the greatest positive integer that divides 1354, 1866, and 2762 leaving the exact same remainder R R R in each case, and determine the value of that remainder R R R .
Step 1: Identify model type: Because the remainder r r r is identical but unknown, compute the HCF of the pairwise absolute differences: D 1 = ∣ 1866 − 1354 ∣ = 512 D_1 = |1866 - 1354| = 512 D 1 = ∣1866 − 1354∣ = 512 D 2 = ∣ 2762 − 1866 ∣ = 896 D_2 = |2762 - 1866| = 896 D 2 = ∣2762 − 1866∣ = 896 D 3 = ∣ 2762 − 1354 ∣ = 1408 D_3 = |2762 - 1354| = 1408 D 3 = ∣2762 − 1354∣ = 1408
Step 2: Factorize the differences to find HCF: 512 = 2 9 512 = 2^9 512 = 2 9 896 = 2 7 × 7 = 128 × 7 896 = 2^7 \times 7 = 128 \times 7 896 = 2 7 × 7 = 128 × 7 1408 = 2 7 × 11 = 128 × 11 1408 = 2^7 \times 11 = 128 \times 11 1408 = 2 7 × 11 = 128 × 11 HCF ( 512 , 896 , 1408 ) = 2 7 = 128 \text{HCF}(512, 896, 1408) = 2^7 = 128 HCF ( 512 , 896 , 1408 ) = 2 7 = 128
The greatest dividing number is 128 .
Step 3: Calculate the common remainder R R R : Divide any of the original numbers by 128: 1354 ÷ 128 : 128 × 10 = 1280 1354 \div 128: \quad 128 \times 10 = 1280 1354 ÷ 128 : 128 × 10 = 1280 R = 1354 − 1280 = 74 R = 1354 - 1280 = 74 R = 1354 − 1280 = 74
(Verification: 1866 = 128 × 14 + 74 = 1792 + 74 = 1866 1866 = 128 \times 14 + 74 = 1792 + 74 = 1866 1866 = 128 × 14 + 74 = 1792 + 74 = 1866 ; 2762 = 128 × 21 + 74 = 2688 + 74 = 2762 2762 = 128 \times 21 + 74 = 2688 + 74 = 2762 2762 = 128 × 21 + 74 = 2688 + 74 = 2762 .)
Conclusion: The greatest divisor is 128 , leaving a constant remainder of 74 .
The periodic bells or signal names in these arithmetic examples are fictional timing devices. Real railway signal aspects are not set by a fixed LCM timer; use the numbers only to practise divisibility and periodic-event models.