Study guide

2.1 Number Systems, Divisibility Rules, Prime Factorization & Remainder Theorem

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.1 Number Systems, Divisibility Rules, Prime Factorization & Remainder Theorem

Key Takeaways Explain This Topic AI

Real numbers partition into rational and irrational sets. For an integer N > 1 N>1 N > 1 , primality testing needs prime trial divisors only through ⌊ N ⌋ \lfloor\sqrt{N}\rfloor ⌊ N ​ ⌋ .

Divisibility rules for composite divisors M = a × b M = a \times b M = a × b require testing co-prime factors where gcd ⁡ ( a , b ) = 1 \gcd(a, b) = 1 g cd ( a , b ) = 1 , such as 72 ( 8 × 9 8 \times 9 8 × 9 ), 88 ( 8 × 11 8 \times 11 8 × 11 ), and 99 ( 9 × 11 9 \times 11 9 × 11 ).

Prime divisors utilize specific algorithmic checks: 7 ( a − 2 b a - 2b a − 2 b ), 11 (alternating sum), 13 ( a + 4 b a + 4b a + 4 b ), 17 ( a − 5 b a - 5b a − 5 b ), and 19 ( a + 2 b a + 2b a + 2 b ).

For N factored into distinct prime powers, multiply one plus each exponent to count positive divisors. Multiply each prime’s geometric-series sum to sum divisors; require a positive power of 2 when summing even divisors.

Advanced modular arithmetic relies on negative remainders, Fermat's Little Theorem ( a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p ) ), Euler's Totient Theorem, Wilson's Theorem, and binomial algebraic expansions.

Last updated: October 2026

Mathematical practice context

The numerical railway scenarios in this guide are fictional aptitude exercises. They use the stated idealized assumptions and do not specify actual operating rules, equipment performance, tariffs, staffing norms or engineering designs.

Classification of Numbers & Set Topology

The real number system R \mathbb{R} R comprises all values representing continuous quantities along the number line. It divides into two mutually exclusive sets: rational numbers ( Q \mathbb{Q} Q ) and irrational numbers ( Q ′ \mathbb{Q}' Q ′ ).

Number Sets & Definitions

Natural Numbers ( N \mathbb{N} N ): Counting numbers { 1 , 2 , 3 , 4 , … } \{1, 2, 3, 4, \dots\} { 1 , 2 , 3 , 4 , … } . Natural numbers are used for discrete tallies such as the number of passenger coaches in a rake or signals in a block section.

Whole Numbers ( W \mathbb{W} W ): Natural numbers including zero { 0 , 1 , 2 , 3 , … } \{0, 1, 2, 3, \dots\} { 0 , 1 , 2 , 3 , … } . Zero represents baseline null states, such as zero block failures during a controller's 8-hour shift.

Integers ( Z \mathbb{Z} Z ): Positive and negative whole numbers along with zero { … , − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 , … } \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\} { … , − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 , … } . Integers express timetable deviations, where + 4 +4 + 4 indicates minutes ahead of schedule and − 7 -7 − 7 denotes minutes of operational delay.

Rational Numbers ( Q \mathbb{Q} Q ): Any number expressible in the fractional form p q \frac{p}{q} q p ​ , where p , q ∈ Z p, q \in \mathbb{Z} p , q ∈ Z and q ≠ 0 q \neq 0 q  = 0 . In decimal form, rational numbers either terminate (e.g., 5 8 = 0.625 \frac{5}{8} = 0.625 8 5 ​ = 0.625 ) or form an infinitely repeating periodic sequence (e.g., 4 11 = 0. 36 ‾ \frac{4}{11} = 0.\overline{36} 11 4 ​ = 0. 36 ).

Irrational Numbers ( Q ′ \mathbb{Q}' Q ′ ): Real numbers that cannot be represented as a ratio of integers. Their decimal expansions are non-terminating and non-repeating (e.g., 2 , 3 , π \sqrt{2}, \sqrt{3}, \pi 2 ​ , 3 ​ , π ). For example, a square with unit-length sides has an irrational diagonal length 2 \sqrt{2} 2 ​ .

Real Numbers ( R \mathbb{R} R ): The union of all rational and irrational numbers ( R = Q ∪ Q ′ \mathbb{R} = \mathbb{Q} \cup \mathbb{Q}' R = Q ∪ Q ′ ).

Prime Numbers: Integers greater than 1 that possess exactly two distinct positive divisors: 1 and the number itself. The integer 2 is the smallest prime number and the only even prime. The number 1 is neither prime nor composite.

Composite Numbers: Integers greater than 1 possessing more than two distinct positive divisors. The smallest composite integer is 4.

Co-prime Numbers (Relatively Prime): Any pair of integers a a a and b b b whose greatest common divisor is 1, denoted as gcd ⁡ ( a , b ) = 1 \gcd(a, b) = 1 g cd ( a , b ) = 1 . The individual numbers need not be primes (e.g., 8 and 15 are co-prime because gcd ⁡ ( 8 , 15 ) = 1 \gcd(8, 15) = 1 g cd ( 8 , 15 ) = 1 , even though both are composite).

Twin Primes: Pairs of prime numbers that differ by exactly 2, such as ( 3 , 5 ) , ( 5 , 7 ) , ( 11 , 13 ) , ( 17 , 19 ) , ( 29 , 31 ) , (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ( 3 , 5 ) , ( 5 , 7 ) , ( 11 , 13 ) , ( 17 , 19 ) , ( 29 , 31 ) , and ( 41 , 43 ) (41, 43) ( 41 , 43 ) .

Number Classification Set Symbol Defining Constraint Operational Railway Example

Natural Numbers N \mathbb{N} N { 1 , 2 , 3 , … } \{1, 2, 3, \dots\} { 1 , 2 , 3 , … } Count of freight wagons in a consist

Whole Numbers W \mathbb{W} W { 0 , 1 , 2 , … } \{0, 1, 2, \dots\} { 0 , 1 , 2 , … } Number of signal failures recorded on a branch line

Integers Z \mathbb{Z} Z { … , − 1 , 0 , 1 , … } \{\dots, -1, 0, 1, \dots\} { … , − 1 , 0 , 1 , … } Variance from working timetable arrival times (minutes)

Rational Numbers Q \mathbb{Q} Q p / q , q ≠ 0 p/q, q \neq 0 p / q , q  = 0 Ruling track gradient ratio ( 1 / 150 1/150 1/150 ) or sectional speed

Irrational Numbers Q ′ \mathbb{Q}' Q ′ Non-terminating, non-repeating Diagonal of a unit square ( 2 \sqrt{2} 2 ​ )

Co-prime Integers Pair ( a , b ) (a, b) ( a , b ) gcd ⁡ ( a , b ) = 1 \gcd(a, b) = 1 g cd ( a , b ) = 1 Factor decomposition for compound divisibility testing

Primality Testing Algorithm

First reject every integer N ≤ 1 N\le1 N ≤ 1 as nonprime. For an integer N > 1 N>1 N > 1 , test primality without exhaustive trial division as follows:

Find the integer floor of the square root of N N N : K = ⌊ N ⌋ K = \lfloor\sqrt{N}\rfloor K = ⌊ N ​ ⌋ .

Test divisibility of N N N only by prime numbers less than or equal to K K K .

For an integer N > 1 N > 1 N > 1 , if no prime p ≤ K p \le K p ≤ K divides N N N , then N N N is prime. Zero, one and negative integers are not primes. +-----------------------------------------------------------------------------+

  • | PRIMALITY TESTING FLOWCHART |
  • +-----------------------------------------------------------------------------+
  • | Given Integer N > 1 |
  • | │ |
  • | ▼ |
  • | Calculate K = floor(sqrt(N)) |
  • | │ |
  • | ▼ |
  • | List all prime numbers p <= K |
  • | │ |
  • | ├──> Does any prime p divide N evenly (N mod p == 0)? |
  • | │ │ |
  • | │ ├──> YES: N is COMPOSITE |
  • | │ │ |
  • | │ └──> NO: N is PRIME |
  • +-----------------------------------------------------------------------------+

Note

Mathematical Justification: Every composite number N N N can be factored into a product of two integers a × b = N a \times b = N a × b = N . If both factors were strictly greater than N \sqrt{N} N ​ , their product would exceed N N N ( a × b > N × N = N a \times b > \sqrt{N} \times \sqrt{N} = N a × b > N ​ × N ​ = N ), which is a contradiction. Thus, at least one prime factor must satisfy p ≤ N p \le \sqrt{N} p ≤ N ​ .

Divisibility Rules from 2 to 19

Divisibility tests help check options and factor expressions without performing full long division.

  • Divisor Divisibility Criterion Algebraic Test / Shortcut
  • 2 Last digit is even ( 0 , 2 , 4 , 6 , 8 0, 2, 4, 6, 8 0 , 2 , 4 , 6 , 8 ) Unit digit divisible by 2
  • 3 Sum of digits is divisible by 3 ∑ d i ≡ 0 ( m o d 3 ) \sum d_i \equiv 0 \pmod 3 ∑ d i ​ ≡ 0 ( mod 3 )

4 Number formed by last two digits is divisible by 4 (or ends in 00) 10 d 1 + d 0 ≡ 0 ( m o d 4 ) 10d_1 + d_0 \equiv 0 \pmod 4 10 d 1 ​ + d 0 ​ ≡ 0 ( mod 4 )

5 Last digit is 0 or 5 d 0 ∈ { 0 , 5 } d_0 \in \{0, 5\} d 0 ​ ∈ { 0 , 5 }

6 Simultaneously divisible by both 2 and 3 Even number and ∑ d i ≡ 0 ( m o d 3 ) \sum d_i \equiv 0 \pmod 3 ∑ d i ​ ≡ 0 ( mod 3 )

7 Truncate last digit, double it, and subtract from remaining number; result is divisible by 7 (or 0) 10 a + b → a − 2 b ( m o d 7 ) 10a + b \to a - 2b \pmod 7 10 a + b → a − 2 b ( mod 7 )

8 Number formed by last three digits is divisible by 8 (or ends in 000) 100 d 2 + 10 d 1 + d 0 ≡ 0 ( m o d 8 ) 100d_2 + 10d_1 + d_0 \equiv 0 \pmod 8 100 d 2 ​ + 10 d 1 ​ + d 0 ​ ≡ 0 ( mod 8 )

  • 9 Sum of digits is divisible by 9 ∑ d i ≡ 0 ( m o d 9 ) \sum d_i \equiv 0 \pmod 9 ∑ d i ​ ≡ 0 ( mod 9 )
  • 10 Last digit is 0 d 0 = 0 d_0 = 0 d 0 ​ = 0

11 Difference between sum of digits in odd places and even places is 0 or a multiple of 11 ∣ ∑ odd d i − ∑ even d i ∣ ≡ 0 ( m o d 11 ) \lvert \sum_{\text{odd}} d_i - \sum_{\text{even}} d_i \rvert \equiv 0 \pmod{11} ∣ ∑ odd ​ d i ​ − ∑ even ​ d i ​ ∣ ≡ 0 ( mod 11 )

12 Simultaneously divisible by 3 and 4 gcd ⁡ ( 3 , 4 ) = 1 \gcd(3, 4) = 1 g cd ( 3 , 4 ) = 1

13 Truncate last digit, multiply by 4, and add to remaining number; result is divisible by 13 10 a + b → a + 4 b ( m o d 13 ) 10a + b \to a + 4b \pmod{13} 10 a + b → a + 4 b ( mod 13 )

  • 14 Simultaneously divisible by 2 and 7 gcd ⁡ ( 2 , 7 ) = 1 \gcd(2, 7) = 1 g cd ( 2 , 7 ) = 1
  • 15 Simultaneously divisible by 3 and 5 gcd ⁡ ( 3 , 5 ) = 1 \gcd(3, 5) = 1 g cd ( 3 , 5 ) = 1

16 Number formed by last four digits is divisible by 16 (or ends in 0000) 1000 d 3 + 100 d 2 + 10 d 1 + d 0 ≡ 0 ( m o d 16 ) 1000d_3 + 100d_2 + 10d_1 + d_0 \equiv 0 \pmod{16} 1000 d 3 ​ + 100 d 2 ​ + 10 d 1 ​ + d 0 ​ ≡ 0 ( mod 16 )

17 Truncate last digit, multiply by 5, and subtract from remaining number; result is divisible by 17 10 a + b → a − 5 b ( m o d 17 ) 10a + b \to a - 5b \pmod{17} 10 a + b → a − 5 b ( mod 17 )

18 Simultaneously divisible by 2 and 9 gcd ⁡ ( 2 , 9 ) = 1 \gcd(2, 9) = 1 g cd ( 2 , 9 ) = 1

19 Truncate last digit, double it, and add to remaining number; result is divisible by 19 10 a + b → a + 2 b ( m o d 19 ) 10a + b \to a + 2b \pmod{19} 10 a + b → a + 2 b ( mod 19 )

In-Depth Modular Mechanisms for Prime Divisors

For any two-part split of integer N = 10 a + b N = 10a + b N = 10 a + b , where b b b is the units digit and a a a is the truncated leading number:

Divisibility by 7: 10 a + b ≡ 0 ( m o d 7 ) ⟺ 3 a + b ≡ 0 ⟺ − 4 a + b ≡ 0 ⟺ a − 2 b ≡ 0 ( m o d 7 ) 10a + b \equiv 0 \pmod 7 \iff 3a + b \equiv 0 \iff -4a + b \equiv 0 \iff a - 2b \equiv 0 \pmod 7 10 a + b ≡ 0 ( mod 7 ) ⟺ 3 a + b ≡ 0 ⟺ − 4 a + b ≡ 0 ⟺ a − 2 b ≡ 0 ( mod 7 ) . Example: Test 2 , 429 2,429 2 , 429 : 242 − 2 ( 9 ) = 224 242 - 2(9) = 224 242 − 2 ( 9 ) = 224 ; next step: 22 − 2 ( 4 ) = 14 22 - 2(4) = 14 22 − 2 ( 4 ) = 14 . Since 14 14 14 is divisible by 7, 2 , 429 2,429 2 , 429 is divisible by 7.

Divisibility by 13: 10 a + b ≡ 0 ( m o d 13 ) ⟺ − 3 a + b ≡ 0 ⟺ 9 a − 3 b ≡ 0 ⟺ a + 4 b ≡ 0 ( m o d 13 ) 10a + b \equiv 0 \pmod{13} \iff -3a + b \equiv 0 \iff 9a - 3b \equiv 0 \iff a + 4b \equiv 0 \pmod{13} 10 a + b ≡ 0 ( mod 13 ) ⟺ − 3 a + b ≡ 0 ⟺ 9 a − 3 b ≡ 0 ⟺ a + 4 b ≡ 0 ( mod 13 ) . Example: Test 1 , 014 1,014 1 , 014 : 101 + 4 ( 4 ) = 117 101 + 4(4) = 117 101 + 4 ( 4 ) = 117 ; next step: 11 + 4 ( 7 ) = 39 11 + 4(7) = 39 11 + 4 ( 7 ) = 39 . Since 39 = 13 × 3 39 = 13 \times 3 39 = 13 × 3 , 1 , 014 1,014 1 , 014 is divisible by 13.

Divisibility by 17: 10 a + b ≡ 0 ( m o d 17 ) ⟺ 10 a + b − 51 b = 10 ( a − 5 b ) ≡ 0 ⟺ a − 5 b ≡ 0 ( m o d 17 ) 10a + b \equiv 0 \pmod{17} \iff 10a + b - 51b = 10(a - 5b) \equiv 0 \iff a - 5b \equiv 0 \pmod{17} 10 a + b ≡ 0 ( mod 17 ) ⟺ 10 a + b − 51 b = 10 ( a − 5 b ) ≡ 0 ⟺ a − 5 b ≡ 0 ( mod 17 ) . Example: Test 2 , 261 2,261 2 , 261 : 226 − 5 ( 1 ) = 221 226 - 5(1) = 221 226 − 5 ( 1 ) = 221 ; next step: 22 − 5 ( 1 ) = 17 22 - 5(1) = 17 22 − 5 ( 1 ) = 17 . Since 17 is divisible by 17, 2 , 261 2,261 2 , 261 is divisible by 17.

Divisibility by 19: 10 a + b ≡ 0 ( m o d 19 ) ⟺ 10 a + b + 19 b = 10 ( a + 2 b ) ≡ 0 ⟺ a + 2 b ≡ 0 ( m o d 19 ) 10a + b \equiv 0 \pmod{19} \iff 10a + b + 19b = 10(a + 2b) \equiv 0 \iff a + 2b \equiv 0 \pmod{19} 10 a + b ≡ 0 ( mod 19 ) ⟺ 10 a + b + 19 b = 10 ( a + 2 b ) ≡ 0 ⟺ a + 2 b ≡ 0 ( mod 19 ) . Example: Test 1 , 083 1,083 1 , 083 : 108 + 2 ( 3 ) = 114 108 + 2(3) = 114 108 + 2 ( 3 ) = 114 ; next step: 11 + 2 ( 4 ) = 19 11 + 2(4) = 19 11 + 2 ( 4 ) = 19 . Since 19 is divisible by 19, 1 , 083 1,083 1 , 083 is divisible by 19.

Compound Divisibility: 72, 88, and 99 Rules

To test divisibility by a composite M M M using two factors whose product is M M M , choose a , b a,b a , b such that gcd ⁡ ( a , b ) = 1 \gcd(a, b) = 1 g cd ( a , b ) = 1 .

Warning

Testing divisibility by 24 using factors 4 and 6 is a catastrophic error because gcd ⁡ ( 4 , 6 ) = 2 ≠ 1 \gcd(4, 6) = 2 \neq 1 g cd ( 4 , 6 ) = 2  = 1 . The number 36 is divisible by 4 and 6, yet 36 / 24 = 1.5 36 / 24 = 1.5 36/24 = 1.5 . Divisibility by 24 requires co-prime factors 3 and 8 ( gcd ⁡ ( 3 , 8 ) = 1 \gcd(3, 8) = 1 g cd ( 3 , 8 ) = 1 ).

Three Composite Divisor Examples

Divisibility by 72 ( 8 × 9 8 \times 9 8 × 9 ):

Apply the rule for 8: The number formed by the last three digits must be divisible by 8.

Apply the rule for 9: The sum of all digits must be divisible by 9.

Divisibility by 88 ( 8 × 11 8 \times 11 8 × 11 ):

Apply the rule for 8: The last three digits must form a number divisible by 8.

Apply the rule for 11: The alternating digital sum ∣ ∑ odd − ∑ even ∣ ≡ 0 ( m o d 11 ) |\sum_{\text{odd}} - \sum_{\text{even}}| \equiv 0 \pmod{11} ∣ ∑ odd ​ − ∑ even ​ ∣ ≡ 0 ( mod 11 ) .

Divisibility by 99 ( 9 × 11 9 \times 11 9 × 11 ):

Apply the rule for 9: The total sum of digits must be divisible by 9.

Apply the rule for 11: The alternating digital sum must be 0 or a multiple of 11.

Canonical Prime Factorization & Factor Functions

By the Fundamental Theorem of Arithmetic, every integer N > 1 N > 1 N > 1 can be uniquely factored into prime powers: N = p 1 a ⋅ p 2 b ⋅ p 3 c ⋯ p k m N = p_1^{a} \cdot p_2^{b} \cdot p_3^{c} \cdots p_k^{m} N = p 1 a ​ ⋅ p 2 b ​ ⋅ p 3 c ​ ⋯ p k m ​

where p 1 < p 2 < ⋯ < p k p_1 < p_2 < \dots < p_k p 1 ​ < p 2 ​ < ⋯ < p k ​ are distinct prime numbers, and a , b , c , … , m a, b, c, \dots, m a , b , c , … , m are positive integers. +-----------------------------------------------------------------------------+

  • | FACTOR COUNTING & SUMMATION FORMULAS |
  • +-----------------------------------------------------------------------------+
  • | Total Number of Factors: |
  • | T(N) = (a + 1)(b + 1)(c + 1)...(m + 1) |
  • | |
  • | Number of Odd Factors (assuming p_1 = 2): |
  • | T_odd(N) = (b + 1)(c + 1)...(m + 1) |
  • | |
  • | Number of Even Factors: |
  • | T_even(N) = a(b + 1)(c + 1)...(m + 1) = T(N) - T_odd(N) |
  • | |
  • | Sum of All Factors: |
  • | S(N) = [(p_1^(a+1) - 1)/(p_1 - 1)] * [(p_2^(b+1) - 1)/(p_2 - 1)] * ... |
  • | |
  • | Product of All Factors: |
  • | P(N) = N^(T(N) / 2) |
  • +-----------------------------------------------------------------------------+

Factor Structure Analysis for N = 2 a ⋅ p 2 b ⋅ p 3 c N = 2^a \cdot p_2^b \cdot p_3^c N = 2 a ⋅ p 2 b ​ ⋅ p 3 c ​

Even Factors: An even factor must contain at least one factor of 2. Hence, the exponent of 2 can take a a a values { 1 , 2 , … , a } \{1, 2, \dots, a\} { 1 , 2 , … , a } instead of ( a + 1 ) (a+1) ( a + 1 ) values. Therefore, T even = a ( b + 1 ) ( c + 1 ) T_{\text{even}} = a(b+1)(c+1) T even ​ = a ( b + 1 ) ( c + 1 ) .

Odd Factors: An odd factor cannot contain any factor of 2. The exponent of 2 must be 0 (1 choice). Therefore, T odd = ( b + 1 ) ( c + 1 ) T_{\text{odd}} = (b+1)(c+1) T odd ​ = ( b + 1 ) ( c + 1 ) .

Sum of Even Factors: S even ( N ) = ( 2 1 + 2 2 + ⋯ + 2 a ) × ( p 2 b + 1 − 1 p 2 − 1 ) × ( p 3 c + 1 − 1 p 3 − 1 ) S_{\text{even}}(N) = (2^1 + 2^2 + \dots + 2^a) \times \left(\frac{p_2^{b+1}-1}{p_2-1}\right) \times \left(\frac{p_3^{c+1}-1}{p_3-1}\right) S even ​ ( N ) = ( 2 1 + 2 2 + ⋯ + 2 a ) × ( p 2 ​ − 1 p 2 b + 1 ​ − 1 ​ ) × ( p 3 ​ − 1 p 3 c + 1 ​ − 1 ​ )

Sum of Odd Factors: S odd ( N ) = ( 2 0 ) × ( p 2 b + 1 − 1 p 2 − 1 ) × ( p 3 c + 1 − 1 p 3 − 1 ) S_{\text{odd}}(N) = (2^0) \times \left(\frac{p_2^{b+1}-1}{p_2-1}\right) \times \left(\frac{p_3^{c+1}-1}{p_3-1}\right) S odd ​ ( N ) = ( 2 0 ) × ( p 2 ​ − 1 p 2 b + 1 ​ − 1 ​ ) × ( p 3 ​ − 1 p 3 c + 1 ​ − 1 ​ )

  • Remainder Theorems & Modular Arithmetic
  • Division Algorithm

For any integer dividend N N N and positive divisor D D D , there exist unique integers Q Q Q (quotient) and R R R (remainder) such that: N = D × Q + R , where 0 ≤ R < D N = D \times Q + R, \quad \text{where } 0 \le R < D N = D × Q + R , where 0 ≤ R < D

The Negative Remainder Method

For the displayed shortcut, choose a negative representative r satisfying -D < r < 0. If a representative lies outside this interval, reduce it modulo D first.

When the dividend is just below a multiple of the divisor, modular calculations are dramatically simplified by using a negative remainder: R positive = D − ∣ R negative ∣ R_{\text{positive}} = D - |R_{\text{negative}}| R positive ​ = D − ∣ R negative ​ ∣

For example, 67 ÷ 68 67 \div 68 67 ÷ 68 has a remainder of 67 67 67 , which is congruent to − 1 ( m o d 68 ) -1 \pmod{68} − 1 ( mod 68 ) .

Fermat's Little Theorem (FLT)

If p p p is a prime number and a a a is an integer co-prime to p p p ( gcd ⁡ ( a , p ) = 1 \gcd(a, p) = 1 g cd ( a , p ) = 1 ): a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p )

Consequently, to compute a n ( m o d p ) a^n \pmod p a n ( mod p ) , reduce the exponent modulo ( p − 1 ) (p - 1) ( p − 1 ) : a n ≡ a n m o d ( p − 1 ) ( m o d p ) a^n \equiv a^{n \bmod (p - 1)} \pmod p a n ≡ a n mod ( p − 1 ) ( mod p )

Euler's Totient Theorem

For any modulus m > 1 m > 1 m > 1 and integer a a a satisfying gcd ⁡ ( a , m ) = 1 \gcd(a, m) = 1 g cd ( a , m ) = 1 : a ϕ ( m ) ≡ 1 ( m o d m ) a^{\phi(m)} \equiv 1 \pmod m a ϕ ( m ) ≡ 1 ( mod m )

where ϕ ( m ) \phi(m) ϕ ( m ) is Euler's totient function, which counts integers in { 1 , 2 , … , m } \{1, 2, \dots, m\} { 1 , 2 , … , m } co-prime to m m m . For prime-factorized m = p 1 k 1 p 2 k 2 ⋯ p r k r m = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} m = p 1 k 1 ​ ​ p 2 k 2 ​ ​ ⋯ p r k r ​ ​ : ϕ ( m ) = m ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) ⋯ ( 1 − 1 p r ) \phi(m) = m \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_r}\right) ϕ ( m ) = m ( 1 − p 1 ​ 1 ​ ) ( 1 − p 2 ​ 1 ​ ) ⋯ ( 1 − p r ​ 1 ​ )

Wilson's Theorem

If p p p is a prime number, then: ( p − 1 ) ! ≡ − 1 ≡ p − 1 ( m o d p ) (p - 1)! \equiv -1 \equiv p - 1 \pmod p ( p − 1 )! ≡ − 1 ≡ p − 1 ( mod p )

Dividing both sides by ( p − 1 ) ≡ − 1 ( m o d p ) (p - 1) \equiv -1 \pmod p ( p − 1 ) ≡ − 1 ( mod p ) gives the useful corollary: ( p − 2 ) ! ≡ 1 ( m o d p ) (p - 2)! \equiv 1 \pmod p ( p − 2 )! ≡ 1 ( mod p )

Polynomial & Binomial Remainder Theorems

In the integer-divisor examples below, assume x is an integer greater than 1 and n is a positive integer.

( x + 1 ) n / x (x + 1)^n / x ( x + 1 ) n / x : Leaves a remainder of 1 n = 1 1^n = 1 1 n = 1 for all integer n ≥ 1 n \ge 1 n ≥ 1 .

( x − 1 ) n / x (x - 1)^n / x ( x − 1 ) n / x : Leaves a remainder of ( − 1 ) n (-1)^n ( − 1 ) n . If n n n is even, remainder is 1 1 1 . If n n n is odd, remainder is − 1 ≡ x − 1 -1 \equiv x - 1 − 1 ≡ x − 1 .

Algebraic Factorization Properties:

( a n + b n ) (a^n + b^n) ( a n + b n ) is always divisible by ( a + b ) (a + b) ( a + b ) whenever n n n is odd .

( a n − b n ) (a^n - b^n) ( a n − b n ) is always divisible by ( a − b ) (a - b) ( a − b ) for all natural numbers n n n .

( a n − b n ) (a^n - b^n) ( a n − b n ) is always divisible by both ( a − b ) (a - b) ( a − b ) and ( a + b ) (a + b) ( a + b ) whenever n n n is even .

  • Worked Examples
  • Worked Example 1: Rolling Stock Identification Audit (Divisibility by 88)

Problem: A computerized railway automated wagon management system scans an 8-digit rolling stock serial code as 342 x 18 y 6 342x18y6 342 x 18 y 6 . In this fictional arithmetic exercise, the code is required to be divisible by 88. If x x x and y y y are single decimal digits, find the maximum possible value of ( 3 x + 2 y ) (3x + 2y) ( 3 x + 2 y ) .

Step 1: Decompose 88 into co-prime divisors: 88 = 8 × 11 , gcd ⁡ ( 8 , 11 ) = 1 88 = 8 \times 11, \quad \gcd(8, 11) = 1 88 = 8 × 11 , g cd ( 8 , 11 ) = 1

Step 2: Apply divisibility by 8 to the last three digits ( 8 y 6 8y6 8 y 6 ): The three-digit number 8 y 6 8y6 8 y 6 must be divisible by 8.

Since 800 800 800 is divisible by 8, the two-digit ending y 6 y6 y 6 must be divisible by 8.

Multiples of 8 ending in 6 between 00 and 99 are: 16 , 56 , 96 16, 56, 96 16 , 56 , 96 .

Therefore, y ∈ { 1 , 5 , 9 } y \in \{1, 5, 9\} y ∈ { 1 , 5 , 9 } .

Step 3: Evaluate Candidate Values for x x x under each y y y via Rule for 11: Number: 342 x 18 y 6 3 4 2 x 1 8 y 6 342 x 18 y 6 .

Sum of digits at odd places (from right): S 1 = 6 + 8 + x + 4 = 18 + x S_1 = 6 + 8 + x + 4 = 18 + x S 1 ​ = 6 + 8 + x + 4 = 18 + x .

Sum of digits at even places (from right): S 2 = y + 1 + 2 + 3 = 6 + y S_2 = y + 1 + 2 + 3 = 6 + y S 2 ​ = y + 1 + 2 + 3 = 6 + y .

Difference: D = S 1 − S 2 = ( 18 + x ) − ( 6 + y ) = 12 + x − y D = S_1 - S_2 = (18 + x) - (6 + y) = 12 + x - y D = S 1 ​ − S 2 ​ = ( 18 + x ) − ( 6 + y ) = 12 + x − y .

For divisibility by 11, 12 + x − y 12 + x - y 12 + x − y must be a multiple of 11.

Case 1: y = 9 y = 9 y = 9 (maximizes y y y ): 12 + x − 9 = 3 + x 12 + x - 9 = 3 + x 12 + x − 9 = 3 + x For $3 + x$ to be a multiple of 11, $3 + x = 11 \implies x = 8$.

Calculate: $3x + 2y = 3(8) + 2(9) = 24 + 18 = 42$.

Case 2: y = 5 y = 5 y = 5 : 12 + x − 5 = 7 + x 12 + x - 5 = 7 + x 12 + x − 5 = 7 + x For $7 + x = 11 \implies x = 4$.

Calculate: $3x + 2y = 3(4) + 2(5) = 12 + 10 = 22$.

Case 3: y = 1 y = 1 y = 1 : 12 + x − 1 = 11 + x 12 + x - 1 = 11 + x 12 + x − 1 = 11 + x For $11 + x$ to be a multiple of 11, $x = 0$ (since $x < 10$).

Calculate: $3x + 2y = 3(0) + 2(1) = 2$.

Conclusion: The maximum possible value of ( 3 x + 2 y ) (3x + 2y) ( 3 x + 2 y ) is 42 (with x = 8 , y = 9 x = 8, y = 9 x = 8 , y = 9 ).

Worked Example 2: Complete Canonical Factor Analysis of N = 3600 N = 3600 N = 3600

Problem: For the integer N = 3600 N = 3600 N = 3600 , determine: (a) Total number of factors, (b) Number of even factors, (c) Number of odd factors, (d) Sum of all factors, and (e) Sum of even factors.

Step 1: Canonical Prime Factorization: 3600 = 36 × 100 = ( 2 2 × 3 2 ) × ( 2 2 × 5 2 ) = 2 4 × 3 2 × 5 2 3600 = 36 \times 100 = (2^2 \times 3^2) \times (2^2 \times 5^2) = 2^4 \times 3^2 \times 5^2 3600 = 36 × 100 = ( 2 2 × 3 2 ) × ( 2 2 × 5 2 ) = 2 4 × 3 2 × 5 2

Here p 1 = 2 , a = 4 p_1 = 2, a = 4 p 1 ​ = 2 , a = 4 ; p 2 = 3 , b = 2 p_2 = 3, b = 2 p 2 ​ = 3 , b = 2 ; p 3 = 5 , c = 2 p_3 = 5, c = 2 p 3 ​ = 5 , c = 2 .

Step 2: Total number of factors: T ( 3600 ) = ( 4 + 1 ) ( 2 + 1 ) ( 2 + 1 ) = 5 × 3 × 3 = 45 T(3600) = (4 + 1)(2 + 1)(2 + 1) = 5 \times 3 \times 3 = 45 T ( 3600 ) = ( 4 + 1 ) ( 2 + 1 ) ( 2 + 1 ) = 5 × 3 × 3 = 45

Step 3: Number of odd factors: Exclude prime factor 2 entirely (set exponent of 2 to 0): T odd = ( 2 + 1 ) ( 2 + 1 ) = 3 × 3 = 9 T_{\text{odd}} = (2 + 1)(2 + 1) = 3 \times 3 = 9 T odd ​ = ( 2 + 1 ) ( 2 + 1 ) = 3 × 3 = 9

Step 4: Number of even factors: T even = T − T odd = 45 − 9 = 36 T_{\text{even}} = T - T_{\text{odd}} = 45 - 9 = 36 T even ​ = T − T odd ​ = 45 − 9 = 36

(Verification: a ( b + 1 ) ( c + 1 ) = 4 × 3 × 3 = 36 a(b+1)(c+1) = 4 \times 3 \times 3 = 36 a ( b + 1 ) ( c + 1 ) = 4 × 3 × 3 = 36 .)

Step 5: Sum of all factors: S ( 3600 ) = ( 2 5 − 1 2 − 1 ) × ( 3 3 − 1 3 − 1 ) × ( 5 3 − 1 5 − 1 ) S(3600) = \left(\frac{2^5 - 1}{2 - 1}\right) \times \left(\frac{3^3 - 1}{3 - 1}\right) \times \left(\frac{5^3 - 1}{5 - 1}\right) S ( 3600 ) = ( 2 − 1 2 5 − 1 ​ ) × ( 3 − 1 3 3 − 1 ​ ) × ( 5 − 1 5 3 − 1 ​ ) S ( 3600 ) = 31 × 26 2 × 124 4 = 31 × 13 × 31 = 403 × 31 = 12 , 493 S(3600) = 31 \times \frac{26}{2} \times \frac{124}{4} = 31 \times 13 \times 31 = 403 \times 31 = 12,493 S ( 3600 ) = 31 × 2 26 ​ × 4 124 ​ = 31 × 13 × 31 = 403 × 31 = 12 , 493

Step 6: Sum of even factors: Sum of powers of 2 starting at 2 1 2^1 2 1 : ( 2 1 + 2 2 + 2 3 + 2 4 ) = 2 + 4 + 8 + 16 = 30 (2^1 + 2^2 + 2^3 + 2^4) = 2 + 4 + 8 + 16 = 30 ( 2 1 + 2 2 + 2 3 + 2 4 ) = 2 + 4 + 8 + 16 = 30 S even = 30 × 13 × 31 = 30 × 403 = 12 , 090 S_{\text{even}} = 30 \times 13 \times 31 = 30 \times 403 = 12,090 S even ​ = 30 × 13 × 31 = 30 × 403 = 12 , 090

(Check: S odd = 1 × 13 × 31 = 403 S_{\text{odd}} = 1 \times 13 \times 31 = 403 S odd ​ = 1 × 13 × 31 = 403 , and 12 , 090 + 403 = 12 , 493 12,090 + 403 = 12,493 12 , 090 + 403 = 12 , 493 .)

Worked Example 3: Modular Remainder Evaluation

Problem: Find the remainder when 19 102 + 28 ! 19^{102} + 28! 1 9 102 + 28 ! is divided by 29.

Step 1: Evaluate 19 102 ( m o d 29 ) 19^{102} \pmod{29} 1 9 102 ( mod 29 ) using Fermat's Little Theorem: The modulus 29 is a prime number, and gcd ⁡ ( 19 , 29 ) = 1 \gcd(19, 29) = 1 g cd ( 19 , 29 ) = 1 .

By Fermat's Little Theorem: 19 29 − 1 = 19 28 ≡ 1 ( m o d 29 ) 19^{29 - 1} = 19^{28} \equiv 1 \pmod{29} 1 9 29 − 1 = 1 9 28 ≡ 1 ( mod 29 ) .

Divide the exponent 102 by 28: 102 = 28 × 3 + 18 102 = 28 \times 3 + 18 102 = 28 × 3 + 18

Therefore: 19 102 = ( 19 28 ) 3 × 19 18 ≡ 1 3 × 19 18 = 19 18 ( m o d 29 ) 19^{102} = (19^{28})^3 \times 19^{18} \equiv 1^3 \times 19^{18} = 19^{18} \pmod{29} 1 9 102 = ( 1 9 28 ) 3 × 1 9 18 ≡ 1 3 × 1 9 18 = 1 9 18 ( mod 29 )

Notice 19 ≡ − 10 ( m o d 29 ) 19 \equiv -10 \pmod{29} 19 ≡ − 10 ( mod 29 ) , and 19 2 = 361 = 29 × 12 + 13 ≡ 13 ( m o d 29 ) 19^2 = 361 = 29 \times 12 + 13 \equiv 13 \pmod{29} 1 9 2 = 361 = 29 × 12 + 13 ≡ 13 ( mod 29 ) .

Also 13 2 = 169 = 29 × 5 + 24 ≡ − 5 ( m o d 29 ) 13^2 = 169 = 29 \times 5 + 24 \equiv -5 \pmod{29} 1 3 2 = 169 = 29 × 5 + 24 ≡ − 5 ( mod 29 ) .

Then 19 18 = ( 19 2 ) 9 ≡ 13 9 = ( 13 2 ) 4 × 13 ≡ ( − 5 ) 4 × 13 = 625 × 13 ( m o d 29 ) 19^{18} = (19^2)^9 \equiv 13^9 = (13^2)^4 \times 13 \equiv (-5)^4 \times 13 = 625 \times 13 \pmod{29} 1 9 18 = ( 1 9 2 ) 9 ≡ 1 3 9 = ( 1 3 2 ) 4 × 13 ≡ ( − 5 ) 4 × 13 = 625 × 13 ( mod 29 ) .

Since 625 = 29 × 21 + 16 ≡ 16 ( m o d 29 ) 625 = 29 \times 21 + 16 \equiv 16 \pmod{29} 625 = 29 × 21 + 16 ≡ 16 ( mod 29 ) : 16 × 13 = 208 = 29 × 7 + 5 ≡ 5 ( m o d 29 ) 16 \times 13 = 208 = 29 \times 7 + 5 \equiv 5 \pmod{29} 16 × 13 = 208 = 29 × 7 + 5 ≡ 5 ( mod 29 )

So 19 102 ≡ 5 ( m o d 29 ) 19^{102} \equiv 5 \pmod{29} 1 9 102 ≡ 5 ( mod 29 ) .

Step 2: Evaluate 28 ! ( m o d 29 ) 28! \pmod{29} 28 ! ( mod 29 ) using Wilson's Theorem: Since 29 is prime, Wilson's Theorem directly dictates: ( 29 − 1 ) ! = 28 ! ≡ − 1 ≡ 28 ( m o d 29 ) (29 - 1)! = 28! \equiv -1 \equiv 28 \pmod{29} ( 29 − 1 )! = 28 ! ≡ − 1 ≡ 28 ( mod 29 )

Step 3: Combine remainders: 19 102 + 28 ! ≡ 5 + ( − 1 ) = 4 ( m o d 29 ) 19^{102} + 28! \equiv 5 + (-1) = 4 \pmod{29} 1 9 102 + 28 ! ≡ 5 + ( − 1 ) = 4 ( mod 29 )

Conclusion: The remainder is 4 .