Study guide

8.2 Division Algorithm, Divisibility Rules, Prime Factorization, Divisors, EBOB (GCD) & EKOK (LCM)

TR-YÖS 2026 — Türkiye Yurt Dışından Öğrenci Kabul Sınavı Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: TR-YÖS Overview, Eligibility & Admissions Strategy

1.1 Current TR-YÖS Identity, Two-Test Blueprint and Admissions 1.2 Candidate Eligibility, Blue Card (Mavi Kart), Dual Citizenship & Registration 1.3 ÖSYM Scoring Mathematics, the 0.5 Raw-Point Rule, 1/4 Penalty & 100-Minute Pacing

2 Chapter 2: Sayısal Yetenek — Number Series, Sequences & Cryptarithmetic

2.1 Linear, Polynomial, Alternating & Recursive Number Series (Sayı Dizileri) 2.2 Number Matrices, Row-Column Operations & Functional Input-Output Tables 2.3 Cryptarithmetic (Harfli İşlemler), Letter-Digit Coding (Şifreler) & Symbolic Operators

3 Chapter 3: Sayısal Yetenek — Visual Series, Analogies & Odd-One-Out

3.1 Figural Series, Angular Rotations, Translations & Element-Counting Rules 3.2 Visual Analogies, Geometric Transformations & Proportion Mapping 3.3 Visual Classification, Topological Invariants & Odd-One-Out (Farklı Olanı Bulma)

4 Chapter 4: Sayısal Yetenek — Visual Matrices, Pattern Completion & Grid Logic

4.1 3x3 Visual Matrices: Superposition, Boolean XOR & Attribute Permutations 4.2 Pattern & Grid Completion (Şekil Tamamlama), Quarter-Tile Symmetry & Tessellations 4.3 Magic Squares, Latin Grids, Sudoku Variants & Relational Matrix Tables

5 Chapter 5: Sayısal Yetenek — 3D Spatial Reasoning: Cubes, Folding & Reflections

5.1 3D Block Stacks, Hidden Cube Counting & Painted Cube Formulas (Küp Sayma) 5.2 Cube Nets (Küp Açılımları), Opposite-Face Parities & 3D Die Rotations 5.3 Paper Folding & Hole Punching (Kağıt Katlama-Kesme), Mirror & Water Reflections

6 Chapter 6: Sayısal Yetenek — Balance Scales, Gears, Clocks & Calendar Logic

6.1 Balance Scales (Teraziler), Symbolic Weight Substitution & Inequality Scales 6.2 Meshed Gears (Çarklar), Concentric Pulleys, Belt Directions & Turn Ratios 6.3 Clock Hand Angles (Saat Problemleri), Modular Calendar Arithmetic & Compass Bearings

7 Chapter 7: Sayısal Yetenek — Data Interpretation, Grid Counting & Deductive Logic

7.1 Bar, Line and Pie Charts & Multi-Table Data Interpretation (Tablo ve Grafikler) 7.2 Grid Perimeter, Shaded Area, Sub-Shape Counting & Shortest Lattice Paths 7.3 Deductive Logic, Linear/Circular Seating Arrangements & Truth-Value Puzzles

8 Chapter 8: Temel Matematik — Number Systems, Base Arithmetic, Divisibility & Rationals

8.1 Number Sets, Parity, Consecutive Sums, Factorials & Base-n Arithmetic (Taban Aritmetiği) 8.2 Division Algorithm, Divisibility Rules, Prime Factorization, Divisors, EBOB (GCD) & EKOK (LCM) 8.3 Rational Numbers, Infinite/Telescoping Fractions & Repeating Decimals (Devirli Ondalık Sayılar)

9 Chapter 9: Temel Matematik — Exponents, Radicals, Factoring, Equations & Inequalities

9.1 Exponential Equations (Üslü Sayılar), Nested Radicals & Rationalizing Denominators 9.2 Algebraic Identities (Çarpanlara Ayırma), Sums and Differences of Cubes & Reciprocal Sums 9.3 First-Degree Linear Systems, Simple Inequalities (Basit Eşitsizlikler) & Absolute Value (Mutlak Değer)

10 Chapter 10: Temel Matematik — Ratios, Proportions & Classic Word Problems

10.1 Ratios, Direct/Inverse/Compound Proportions (Oran-Orantı) & Means 10.2 Number, Fraction, Age (Yaş) & Work/Pipe (İşçi-Havuz) Word Problems 10.3 Percentage, Profit-Loss (Kâr-Zarar), Mixture (Karışım) & Motion (Hareket) Problems

11 Chapter 11: Temel Matematik — Sets, Modular Operations, Functions, Polynomials & Quadratics

11.1 Sets (Kümeler), Cartesian Products, Binary Operations (İşlem) & Modular Arithmetic (Modüler Aritmetik) 11.2 Functions (Fonksiyonlar): Domain/Range, Composition, Inverses & Functional Equations 11.3 Polynomials (Polinomlar), Quadratic Equations, Vieta's Formulas & Parabolas

12 Chapter 12: Temel Matematik — Logarithms, Complex Numbers, Combinatorics, Trigonometry & Calculus

12.1 Logarithms (Logaritma), Complex Numbers & Arithmetic/Geometric Sequences (Diziler) 12.2 Permutations, Combinations, Binomial Expansion & Probability (Olasılık) 12.3 Trigonometry and Optional Calculus Enrichment

13 Chapter 13: Temel Matematik (Geometri) — Angles, Triangles, Similarity, Area & Polygons

13.1 Parallel-Line Angle Rules (Z, U, M, Kalem Ucu), Triangle Angles & Triangle Inequality 13.2 Right Triangles, Euclid's Altitude Laws, Angle Bisectors, Medians, Similarity & Area 13.3 Regular Polygons, Quadrilaterals, Parallelograms, Trapezoids, Rhombuses, Rectangles & Squares

14 Chapter 14: Temel Matematik (Geometri) — Circles, 3D Solids & Analytic Geometry

14.1 Circle Angles, Chords, Tangents, Power of a Point (Kuvvet) & Sector/Annulus Area 14.2 3D Solid Geometry (Katı Cisimler): Prisms, Cylinders, Pyramids, Cones & Spheres 14.3 Analytic Geometry (Analitik Geometri): Points, Lines, Slopes, Point-to-Line Distance & Circles

8.2 Division Algorithm, Divisibility Rules, Prime Factorization, Divisors, EBOB (GCD) & EKOK (LCM)

Key Takeaways Explain This Topic AI

In the Euclidean division A = B ⋅ C + K A = B \cdot C + K A = B ⋅ C + K , the remainder K K K must always satisfy 0 ≤ K < B 0 \le K < B 0 ≤ K < B ; many TR-YÖS extremum division problems hinge on enforcing K < B K < B K < B before substituting values.

When testing divisibility by a composite number M M M , decompose M M M into coprime factors ( EBOB ( a , b ) = 1 \text{EBOB}(a, b) = 1 EBOB ( a , b ) = 1 , such as 36 = 4 × 9 36 = 4 \times 9 36 = 4 × 9 or 45 = 5 × 9 45 = 5 \times 9 45 = 5 × 9 ) and apply last-digit rules ( 2 , 5 , 10 , 4 , 8 2, 5, 10, 4, 8 2 , 5 , 10 , 4 , 8 ) before digit-sum rules ( 3 , 9 , 11 3, 9, 11 3 , 9 , 11 ).

For prime factorization N = p 1 e 1 p 2 e 2 ⋯ p k e k N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} N = p 1 e 1 ​ ​ p 2 e 2 ​ ​ ⋯ p k e k ​ ​ , the number of positive integer divisors is d + ( N ) = ( e 1 + 1 ) ( e 2 + 1 ) ⋯ ( e k + 1 ) d^+(N) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1) d + ( N ) = ( e 1 ​ + 1 ) ( e 2 ​ + 1 ) ⋯ ( e k ​ + 1 ) , the total number of integer divisors is 2 d + ( N ) 2d^+(N) 2 d + ( N ) , and the sum of all integer divisors is 0 0 0 .

For any two positive integers a a a and b b b , a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) a \cdot b = \text{EBOB}(a, b) \cdot \text{EKOK}(a, b) a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) and EBOB ( a , b ) ≤ min ⁡ ( a , b ) ≤ max ⁡ ( a , b ) ≤ EKOK ( a , b ) \text{EBOB}(a, b) \le \min(a, b) \le \max(a, b) \le \text{EKOK}(a, b) EBOB ( a , b ) ≤ min ( a , b ) ≤ max ( a , b ) ≤ EKOK ( a , b ) .

In simultaneous remainder problems A = d 1 x + r 1 = d 2 y + r 2 = d 3 z + r 3 A = d_1 x + r_1 = d_2 y + r_2 = d_3 z + r_3 A = d 1 ​ x + r 1 ​ = d 2 ​ y + r 2 ​ = d 3 ​ z + r 3 ​ where d i − r i = c d_i - r_i = c d i ​ − r i ​ = c is constant, adding c c c to all parts makes A + c A + c A + c a common multiple of EKOK ( d 1 , d 2 , d 3 ) \text{EKOK}(d_1, d_2, d_3) EKOK ( d 1 ​ , d 2 ​ , d 3 ​ ) .

Last updated: October 2026

8.2 Division Algorithm, Divisibility Rules, Prime Factorization, Divisors, EBOB (GCD) & EKOK (LCM)

Number theory questions in the TR-YÖS test structural shortcuts rather than brute-force arithmetic. Whether bounding a variable in a division box, solving for unknown digits in a five-digit number divisible by 36 36 36 , counting the non-prime divisors of 720 720 720 , or synchronizing remainders via EKOK \text{EKOK} EKOK , mastering these four pillars turns lengthy computations into twenty-second solutions.

1. The Euclidean Division Algorithm ( Bölme Algoritması )

When a dividend ( Bölünen , A A A ) is divided by a divisor ( Bölen , B B B ) to produce a quotient ( Bölüm , C C C ) and a remainder ( Kalan , K K K ), two fundamental relationships govern the division box:

  • The Division Identity ( Bölme Özdeşliği ): A = B ⋅ C + K A = B \cdot C + K A = B ⋅ C + K
  • The Strict Remainder Inequality ( Kalan Koşulu ): 0 ≤ K < B 0 \le K < B 0 ≤ K < B

The remainder K K K is strictly less than the divisor B B B . If K = 0 K = 0 K = 0 , we say A A A is exactly divisible by B B B ( B ∣ A B \mid A B ∣ A ).

Classic TR-YÖS Division Traps

Swapping Divisor and Quotient: You may interchange the divisor B B B and the quotient C C C ( A = C ⋅ B + K A = C \cdot B + K A = C ⋅ B + K ) if and only if the remainder is also strictly less than the quotient ( K < C K < C K < C ).

Algebraic Remainder Bounds: Suppose A A A divided by B = 3 x + 4 B = 3x + 4 B = 3 x + 4 gives quotient C = x + 1 C = x + 1 C = x + 1 and remainder K = x 2 K = x^2 K = x 2 for x ∈ N x \in \mathbb{N} x ∈ N . You cannot choose arbitrary values for x x x : the condition K < B K < B K < B forces: x 2 < 3 x + 4 ⟹ x 2 − 3 x − 4 < 0 ⟹ ( x − 4 ) ( x + 1 ) < 0 x^2 < 3x + 4 \implies x^2 - 3x - 4 < 0 \implies (x - 4)(x + 1) < 0 x 2 < 3 x + 4 ⟹ x 2 − 3 x − 4 < 0 ⟹ ( x − 4 ) ( x + 1 ) < 0

Since x ∈ N x \in \mathbb{N} x ∈ N , only x ∈ { 0 , 1 , 2 , 3 } x \in \{0, 1, 2, 3\} x ∈ { 0 , 1 , 2 , 3 } are valid! Thus the maximum possible value of A A A occurs at x = 3 x = 3 x = 3 , giving B = 13 B = 13 B = 13 , C = 4 C = 4 C = 4 , K = 9 K = 9 K = 9 , and A = 13 ( 4 ) + 9 = 61 A = 13(4) + 9 = 61 A = 13 ( 4 ) + 9 = 61 .

Modular Arithmetic of Remainders: The remainder of A ± B A \pm B A ± B , A ⋅ B A \cdot B A ⋅ B , or A n A^n A n when divided by m m m equals the remainder obtained by replacing A A A and B B B with their respective remainders modulo m m m .

  • 2. Divisibility Rules ( Bölünebilme Kuralları )
  • Elementary Rules (By Last Digits vs. By Digit Sums)

Last-Digit Family ( 2 , 5 , 10 , 4 , 8 2, 5, 10, 4, 8 2 , 5 , 10 , 4 , 8 ):

By 2 2 2 : The units digit is even ( { 0 , 2 , 4 , 6 , 8 } \{0, 2, 4, 6, 8\} { 0 , 2 , 4 , 6 , 8 } ).

By 5 5 5 : The units digit is 0 0 0 or 5 5 5 (remainder mod 5 5 5 is determined entirely by the units digit).

By 10 10 10 : The units digit is 0 0 0 (remainder mod 10 10 10 IS the units digit).

By 4 4 4 : The two-digit number formed by the last two digits is divisible by 4 4 4 ( 10 d 1 + d 0 ≡ 2 d 1 + d 0 ( m o d 4 ) 10d_1 + d_0 \equiv 2d_1 + d_0 \pmod 4 10 d 1 ​ + d 0 ​ ≡ 2 d 1 ​ + d 0 ​ ( mod 4 ) ).

By 8 8 8 : The three-digit number formed by the last three digits is divisible by 8 8 8 ( 4 d 2 + 2 d 1 + d 0 ≡ 0 ( m o d 8 ) 4d_2 + 2d_1 + d_0 \equiv 0 \pmod 8 4 d 2 ​ + 2 d 1 ​ + d 0 ​ ≡ 0 ( mod 8 ) ).

Digit-Sum Family ( 3 , 9 , 11 3, 9, 11 3 , 9 , 11 ):

By 3 3 3 (and 9 9 9 ): The sum of all digits ∑ d i \sum d_i ∑ d i ​ is a multiple of 3 3 3 (or 9 9 9 ). The remainder of N N N divided by 3 3 3 or 9 9 9 equals the remainder of ∑ d i \sum d_i ∑ d i ​ divided by 3 3 3 or 9 9 9 .

By 11 11 11 (Alternating Sign Rule): Starting at the units digit (rightmost digit) with a + + + sign and alternating + , − , + , − , … +, -, +, -, \dots + , − , + , − , … from right to left: R 11 ≡ ( d 0 − d 1 + d 2 − d 3 + d 4 − … ) ( m o d 11 ) R_{11} \equiv (d_0 - d_1 + d_2 - d_3 + d_4 - \dots) \pmod{11} R 11 ​ ≡ ( d 0 ​ − d 1 ​ + d 2 ​ − d 3 ​ + d 4 ​ − … ) ( mod 11 ) If this alternating sum is negative, add multiples of $11$ until it falls in $0 \le R_{11} < 11$.

Composite Divisors ( Birleşik Sayılarla Bölünebilme )

A number is divisible by a composite divisor M M M if and only if it is simultaneously divisible by coprime ( aralarında asal ) factors a a a and b b b such that M = a ⋅ b M = a \cdot b M = a ⋅ b and EBOB ( a , b ) = 1 \text{EBOB}(a, b) = 1 EBOB ( a , b ) = 1 :

6 ⟺ 2 and 3 6 \iff 2 \text{ and } 3 6 ⟺ 2 and 3

12 ⟺ 3 and 4 12 \iff 3 \text{ and } 4 12 ⟺ 3 and 4 (never 2 and 6 2 \text{ and } 6 2 and 6 , since EBOB ( 2 , 6 ) = 2 ≠ 1 \text{EBOB}(2,6) = 2 \ne 1 EBOB ( 2 , 6 ) = 2  = 1 !)

  • 15 ⟺ 3 and 5 15 \iff 3 \text{ and } 5 15 ⟺ 3 and 5
  • 18 ⟺ 2 and 9 18 \iff 2 \text{ and } 9 18 ⟺ 2 and 9
  • 30 ⟺ 3 and 10 30 \iff 3 \text{ and } 10 30 ⟺ 3 and 10
  • 36 ⟺ 4 and 9 36 \iff 4 \text{ and } 9 36 ⟺ 4 and 9
  • 45 ⟺ 5 and 9 45 \iff 5 \text{ and } 9 45 ⟺ 5 and 9
  • 90 ⟺ 9 and 10 90 \iff 9 \text{ and } 10 90 ⟺ 9 and 10

Tip

Execution Order: Always apply the last-digit rule ( 2 , 5 , 10 , 4 , 8 2, 5, 10, 4, 8 2 , 5 , 10 , 4 , 8 ) first to narrow the rightmost digit(s) to 1 1 1 or 2 2 2 cases, and only then apply the digit-sum rule ( 3 , 9 , 11 3, 9, 11 3 , 9 , 11 ) to solve for interior digits.

3. Prime Factorization ( Asal Çarpanlara Ayırma ) & Divisor Counting

A prime number ( Asal Sayı ) is an integer p ≥ 2 p \ge 2 p ≥ 2 whose only positive divisors are 1 1 1 and p p p : { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , … } \{2, 3, 5, 7, 11, 13, 17, 19, 23, \dots\} { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , … } . Note that 2 2 2 is the smallest and the only even prime number ( 1 1 1 is not prime!).

Every integer N ≥ 2 N \ge 2 N ≥ 2 has a unique canonical prime factorization: N = p 1 e 1 ⋅ p 2 e 2 ⋯ p k e k N = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} N = p 1 e 1 ​ ​ ⋅ p 2 e 2 ​ ​ ⋯ p k e k ​ ​

where p 1 < p 2 < ⋯ < p k p_1 < p_2 < \dots < p_k p 1 ​ < p 2 ​ < ⋯ < p k ​ are distinct primes and e i ∈ Z + e_i \in \mathbb{Z}^+ e i ​ ∈ Z + . From the exponents e i e_i e i ​ , we extract every divisor property of N N N :

Number of Positive Divisors ( Pozitif Tam Bölen Sayısı — PBS): d + ( N ) = ( e 1 + 1 ) ( e 2 + 1 ) ⋯ ( e k + 1 ) d^+(N) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1) d + ( N ) = ( e 1 ​ + 1 ) ( e 2 ​ + 1 ) ⋯ ( e k ​ + 1 )

Number of Negative Divisors ( Negatif Tam Bölen Sayısı ): d − ( N ) = d + ( N ) d^-(N) = d^+(N) d − ( N ) = d + ( N ) .

Total Number of Integer Divisors ( Tam Bölen Sayısı — TBS): d ( N ) = 2 ⋅ d + ( N ) = 2 ( e 1 + 1 ) ( e 2 + 1 ) ⋯ ( e k + 1 ) d(N) = 2 \cdot d^+(N) = 2(e_1 + 1)(e_2 + 1)\cdots(e_k + 1) d ( N ) = 2 ⋅ d + ( N ) = 2 ( e 1 ​ + 1 ) ( e 2 ​ + 1 ) ⋯ ( e k ​ + 1 )

Sum of All Integer Divisors: Always 0 0 0 , because every positive divisor d d d cancels with its negative counterpart − d -d − d .

Sum of Positive Divisors: σ ( N ) = ( p 1 e 1 + 1 − 1 p 1 − 1 ) ( p 2 e 2 + 1 − 1 p 2 − 1 ) ⋯ ( p k e k + 1 − 1 p k − 1 ) \sigma(N) = \left(\frac{p_1^{e_1+1} - 1}{p_1 - 1}\right)\left(\frac{p_2^{e_2+1} - 1}{p_2 - 1}\right)\cdots\left(\frac{p_k^{e_k+1} - 1}{p_k - 1}\right) σ ( N ) = ( p 1 ​ − 1 p 1 e 1 ​ + 1 ​ − 1 ​ ) ( p 2 ​ − 1 p 2 e 2 ​ + 1 ​ − 1 ​ ) ⋯ ( p k ​ − 1 p k e k ​ + 1 ​ − 1 ​ )

Sum of Non-Prime Integer Divisors: Since positive and negative divisors cancel except that prime divisors are positive, the sum of all integer divisors that are not prime equals − ( p 1 + p 2 + ⋯ + p k ) -(p_1 + p_2 + \dots + p_k) − ( p 1 ​ + p 2 ​ + ⋯ + p k ​ ) !

Product of Positive Divisors: P + ( N ) = N d + ( N ) / 2 P^+(N) = N^{d^+(N)/2} P + ( N ) = N d + ( N ) /2 .

4. Greatest Common Divisor ( EBOB ) & Least Common Multiple ( EKOK )

For positive integers a = ∏ p i α i a = \prod p_i^{\alpha_i} a = ∏ p i α i ​ ​ and b = ∏ p i β i b = \prod p_i^{\beta_i} b = ∏ p i β i ​ ​ : EBOB ( a , b ) = ∏ p i min ⁡ ( α i , β i ) , EKOK ( a , b ) = ∏ p i max ⁡ ( α i , β i ) \text{EBOB}(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}, \qquad \text{EKOK}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)} EBOB ( a , b ) = ∏ p i m i n ( α i ​ , β i ​ ) ​ , EKOK ( a , b ) = ∏ p i m a x ( α i ​ , β i ​ ) ​

Fundamental Laws of EBOB and EKOK

Product Identity (for TWO numbers): a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) a \cdot b = \text{EBOB}(a, b) \cdot \text{EKOK}(a, b) a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) .

Ordering Inequality: EBOB ( a , b ) ≤ min ⁡ ( a , b ) ≤ max ⁡ ( a , b ) ≤ EKOK ( a , b ) \text{EBOB}(a, b) \le \min(a, b) \le \max(a, b) \le \text{EKOK}(a, b) EBOB ( a , b ) ≤ min ( a , b ) ≤ max ( a , b ) ≤ EKOK ( a , b ) .

When a a a and b b b are allowed to be equal ( a = b a = b a = b ), EBOB ( a , b ) = a = b = EKOK ( a , b ) \text{EBOB}(a, b) = a = b = \text{EKOK}(a, b) EBOB ( a , b ) = a = b = EKOK ( a , b ) .

When a ≠ b a \ne b a  = b , to maximize a + b a + b a + b given EKOK ( a , b ) = L \text{EKOK}(a, b) = L EKOK ( a , b ) = L , choose L L L and its largest proper positive divisor; that divisor is L / p L/p L / p for the smallest prime factor p p p of L L L ( L > 1 L>1 L > 1 ). To minimize a + b a + b a + b given EBOB ( a , b ) = G \text{EBOB}(a, b) = G EBOB ( a , b ) = G , choose a = G a = G a = G and b = 2 G b = 2G b = 2 G .

Coprime Numbers ( Aralarında Asal Sayılar ): Two positive integers a a a and b b b are coprime if EBOB ( a , b ) = 1 \text{EBOB}(a, b) = 1 EBOB ( a , b ) = 1 , which implies EKOK ( a , b ) = a ⋅ b \text{EKOK}(a, b) = a \cdot b EKOK ( a , b ) = a ⋅ b . Note that 1 1 1 is coprime with every positive integer , and any two consecutive positive integers ( n n n and n + 1 n+1 n + 1 ) or consecutive odd integers ( 2 n − 1 2n-1 2 n − 1 and 2 n + 1 2n+1 2 n + 1 ) are always coprime!

Constant-Deficit Remainder Problems: To find the smallest positive integer A A A satisfying A = d 1 x + r 1 = d 2 y + r 2 = d 3 z + r 3 A = d_1 x + r_1 = d_2 y + r_2 = d_3 z + r_3 A = d 1 ​ x + r 1 ​ = d 2 ​ y + r 2 ​ = d 3 ​ z + r 3 ​

where d 1 − r 1 = d 2 − r 2 = d 3 − r 3 = c d_1 - r_1 = d_2 - r_2 = d_3 - r_3 = c d 1 ​ − r 1 ​ = d 2 ​ − r 2 ​ = d 3 ​ − r 3 ​ = c , add c c c to every expression so that A + c = d 1 ( x + 1 ) = d 2 ( y + 1 ) = d 3 ( z + 1 ) A + c = d_1(x+1) = d_2(y+1) = d_3(z+1) A + c = d 1 ​ ( x + 1 ) = d 2 ​ ( y + 1 ) = d 3 ​ ( z + 1 ) . Then A + c = k ⋅ EKOK ( d 1 , d 2 , d 3 ) A + c = k \cdot \text{EKOK}(d_1, d_2, d_3) A + c = k ⋅ EKOK ( d 1 ​ , d 2 ​ , d 3 ​ ) for k ∈ Z + k \in \mathbb{Z}^+ k ∈ Z + .

Summary Reference Table

Rule / Property Mathematical Formula Exam Shortcut / Note

Euclidean Division A = B ⋅ C + K A = B \cdot C + K A = B ⋅ C + K with 0 ≤ K < B 0 \le K < B 0 ≤ K < B Always enforce K < B K < B K < B to bound unknown variables

Divisibility by 11 11 11 ( d 0 − d 1 + d 2 − d 3 + … ) ≡ 0 ( m o d 11 ) (d_0 - d_1 + d_2 - d_3 + \dots) \equiv 0 \pmod{11} ( d 0 ​ − d 1 ​ + d 2 ​ − d 3 ​ + … ) ≡ 0 ( mod 11 ) Start with + + + on the rightmost (units) digit

Divisor Counts ( N = ∏ p i e i N = \prod p_i^{e_i} N = ∏ p i e i ​ ​ ) d + ( N ) = ∏ ( e i + 1 ) d^+(N) = \prod (e_i + 1) d + ( N ) = ∏ ( e i ​ + 1 ) ; TBS = 2 d + ( N ) \text{TBS} = 2 d^+(N) TBS = 2 d + ( N ) Sum of all integer divisors is 0 0 0 ; non-prime integer sum is − ∑ p i -\sum p_i − ∑ p i ​

Positive Divisor Sum σ ( N ) = ∏ p i e i + 1 − 1 p i − 1 \sigma(N) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1} σ ( N ) = ∏ p i ​ − 1 p i e i ​ + 1 ​ − 1 ​ Count odd divisors by omitting the prime factor 2 2 2

EBOB / EKOK Identity a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) a \cdot b = \text{EBOB}(a, b) \cdot \text{EKOK}(a, b) a ⋅ b = EBOB ( a , b ) ⋅ EKOK ( a , b ) If EBOB ( a , b ) = 1 \text{EBOB}(a,b) = 1 EBOB ( a , b ) = 1 , then EKOK ( a , b ) = a ⋅ b \text{EKOK}(a,b) = a \cdot b EKOK ( a , b ) = a ⋅ b

  • Worked Examples
  • Worked Example 8.2.1: Multi-Condition Composite Divisibility

Problem: The five-digit number ( 5 a 38 b ) 10 (5a38b)_{10} ( 5 a 38 b ) 10 ​ with distinct digits yields a remainder of 13 13 13 when divided by 36 36 36 . Find the value of the digit a a a .

Solution:

Decompose 36 36 36 into coprime factors 4 4 4 and 9 9 9 , and reduce the remainder 13 13 13 :

Remainder when divided by 4 4 4 : 13 ≡ 1 ( m o d 4 ) 13 \equiv 1 \pmod 4 13 ≡ 1 ( mod 4 ) .

Remainder when divided by 9 9 9 : 13 ≡ 4 ( m o d 9 ) 13 \equiv 4 \pmod 9 13 ≡ 4 ( mod 9 ) .

Apply the mod- 4 4 4 rule to the last two digits ( 8 b ) 10 (8b)_{10} ( 8 b ) 10 ​ first: For ( 8 b ) 10 ≡ 1 ( m o d 4 ) (8b)_{10} \equiv 1 \pmod 4 ( 8 b ) 10 ​ ≡ 1 ( mod 4 ) , since 80 80 80 is a multiple of 4 4 4 , we need b ≡ 1 ( m o d 4 ) b \equiv 1 \pmod 4 b ≡ 1 ( mod 4 ) , which gives b ∈ { 1 , 5 , 9 } b \in \{1, 5, 9\} b ∈ { 1 , 5 , 9 } . Because the digits of ( 5 a 38 b ) 10 (5a38b)_{10} ( 5 a 38 b ) 10 ​ are distinct , b = 5 b = 5 b = 5 is eliminated (since 5 5 5 already appears as the leading digit). Thus b = 1 b = 1 b = 1 or b = 9 b = 9 b = 9 .

Apply the mod- 9 9 9 rule to the digit sum:

Case 1 ( b = 1 b = 1 b = 1 ): Digit sum is 5 + a + 3 + 8 + 1 = 17 + a ≡ 8 + a ( m o d 9 ) 5 + a + 3 + 8 + 1 = 17 + a \equiv 8 + a \pmod 9 5 + a + 3 + 8 + 1 = 17 + a ≡ 8 + a ( mod 9 ) . Setting 8 + a ≡ 4 ( m o d 9 ) 8 + a \equiv 4 \pmod 9 8 + a ≡ 4 ( mod 9 ) yields a = 5 a = 5 a = 5 . However, 5 5 5 is already used in ( 5 a 381 ) 10 (5a381)_{10} ( 5 a 381 ) 10 ​ , violating distinct digits!

Case 2 ( b = 9 b = 9 b = 9 ): Digit sum is 5 + a + 3 + 8 + 9 = 25 + a ≡ 7 + a ( m o d 9 ) 5 + a + 3 + 8 + 9 = 25 + a \equiv 7 + a \pmod 9 5 + a + 3 + 8 + 9 = 25 + a ≡ 7 + a ( mod 9 ) . Setting 7 + a ≡ 4 ( m o d 9 ) 7 + a \equiv 4 \pmod 9 7 + a ≡ 4 ( mod 9 ) yields a = 6 a = 6 a = 6 . Checking distinctness in ( 56389 ) 10 (56389)_{10} ( 56389 ) 10 ​ : all five digits { 5 , 6 , 3 , 8 , 9 } \{5, 6, 3, 8, 9\} { 5 , 6 , 3 , 8 , 9 } are distinct. Thus a = 6 a = 6 a = 6 is the unique valid solution.

Worked Example 8.2.2: Divisor Counting with Embedded Powers of 10 10 10

Problem: Let N = 18 ⋅ 10 n N = 18 \cdot 10^n N = 18 ⋅ 1 0 n be a positive integer ( n ∈ Z + n \in \mathbb{Z}^+ n ∈ Z + ). If N N N has exactly 117 117 117 integer divisors that are not prime , find n n n .

Solution:

Write the canonical prime factorization of N N N : N = ( 2 ⋅ 3 2 ) ⋅ ( 2 ⋅ 5 ) n = 2 n + 1 ⋅ 3 2 ⋅ 5 n N = (2 \cdot 3^2) \cdot (2 \cdot 5)^n = 2^{n+1} \cdot 3^2 \cdot 5^n N = ( 2 ⋅ 3 2 ) ⋅ ( 2 ⋅ 5 ) n = 2 n + 1 ⋅ 3 2 ⋅ 5 n

Relate total integer divisors (TBS) to non-prime integer divisors: The distinct prime divisors of N N N are 2 , 3 , 5 2, 3, 5 2 , 3 , 5 ( 3 3 3 primes in total). Every other integer divisor of N N N (positive or negative) is non-prime: TBS ( N ) − 3 = 117 ⟹ TBS ( N ) = 120 \text{TBS}(N) - 3 = 117 \implies \text{TBS}(N) = 120 TBS ( N ) − 3 = 117 ⟹ TBS ( N ) = 120

Since TBS ( N ) = 2 ⋅ d + ( N ) \text{TBS}(N) = 2 \cdot d^+(N) TBS ( N ) = 2 ⋅ d + ( N ) , the number of positive divisors is d + ( N ) = 60 d^+(N) = 60 d + ( N ) = 60 .

3. Use the PBS formula to solve for n n n : d + ( N ) = ( ( n + 1 ) + 1 ) ( 2 + 1 ) ( n + 1 ) = 3 ( n + 2 ) ( n + 1 ) = 60 d^+(N) = ((n + 1) + 1)(2 + 1)(n + 1) = 3(n + 2)(n + 1) = 60 d + ( N ) = (( n + 1 ) + 1 ) ( 2 + 1 ) ( n + 1 ) = 3 ( n + 2 ) ( n + 1 ) = 60 ( n + 2 ) ( n + 1 ) = 20 = 5 × 4 ⟹ n = 3 (n + 2)(n + 1) = 20 = 5 \times 4 \implies n = 3 ( n + 2 ) ( n + 1 ) = 20 = 5 × 4 ⟹ n = 3

Review the Method

In simultaneous remainder problems A = d 1 x + r 1 = d 2 y + r 2 = d 3 z + r 3 A = d_1 x + r_1 = d_2 y + r_2 = d_3 z + r_3 A = d 1 ​ x + r 1 ​ = d 2 ​ y + r 2 ​ = d 3 ​ z + r 3 ​ where d i − r i = c d_i - r_i = c d i ​ − r i ​ = c is constant, adding c c c to all parts makes A + c A + c A + c a common multiple of EKOK ( d 1 , d 2 , d 3 ) \text{EKOK}(d_1, d_2, d_3) EKOK ( d 1 ​ , d 2 ​ , d 3 ​ ) .

Loading diagram... Step-by-Step Decision Flow for Composite Divisibility Problems