← CLT Prep

CLT: Divisibility as a set of constraints

Use parity, prime powers and residues to identify exactly which integers satisfy a condition.

Updated October 2, 2026

Overview

Integer questions become easier when you stop treating each number as a separate object. Parity sorts integers into two classes; prime factors describe divisibility; remainders sort an infinite list into a small repeating cycle. The useful question is which description fits the information you have. In this lesson you will move from an observation about consecutive integers to a problem where two different divisibility conditions must hold together.

Read what a condition really restricts

Suppose n(n + 1) + 1 is odd. It is tempting to decide that n itself must be odd, because an odd result appears in the question. Instead, examine the product before the addition. Consecutive integers always include an even integer. Their product is therefore even, whether n is even or odd, and adding one makes it odd. The stated condition holds for every integer n; it creates no parity restriction.

Notice the difference between proving something about a product and proving something about each factor. An even product needs at least one even factor, not two. Nor does an even product necessarily contain two factors of 2. For example, n = 1 makes n(n + 1) equal to 2, so a claim that this product must be divisible by 4 fails. A single allowed example can refute a universal claim, but the consecutive-integer argument establishes the true claim for all integers.

Build the least common multiple from required powers

Now consider a positive integer divisible by both 18 and 40. The word “both” means neither requirement may be lost. Factor the numbers: 18 requires one factor of 2 and two factors of 3; 40 requires three factors of 2 and one factor of 5. The least number meeting both requirements contains the largest required power of each prime: 2³ × 3² × 5 = 360.

This construction explains why multiplying 18 by 40 gives an unnecessarily large answer. Their shared factor of 2 has been supplied twice, although the requirements do not demand that duplication. At the other extreme, 180 is divisible by 18 but not by 40: it has too few factors of 2. Check a proposed least common multiple in two stages. First verify that each original divisor divides it. Then ask whether any prime factor could be removed while keeping both divisions exact. That second question addresses “least,” not merely “common.”

Combine a remainder condition with a bounded list

For the more demanding problem, n is positive, less than 100, divisible by 3, and makes n² + 3n divisible by 7. Factor the polynomial as n(n + 3). Because 7 is prime, the product is divisible by 7 only when n or n + 3 is divisible by 7. Thus n leaves remainder 0 or 4 on division by 7.

The first class intersects multiples of 3 at 21, 42, 63 and 84. For the second class, the multiples of 3 with remainder 4 modulo 7 are 18, 39, 60 and 81. These classes cannot overlap because a number cannot have two different remainders on division by 7. They contribute four values each, giving eight in total. The endpoint restriction matters: this is a count within a stated interval, not a claim about all integers. Writing the lists makes both completeness and the absence of duplication visible.

Choose a representation and check its reach

The closest mistake in the final problem is to find one valid residue class, count four numbers, and stop. That work is correct as far as it goes, but the factored product has two ways to be divisible by 7. Train yourself to mark every branch created by an “or,” then return to the original “and” conditions to filter each branch.

For a fresh integer problem, decide first whether you need a universal argument, a least construction, or a finite count. Use parity for even–odd structure, prime powers for simultaneous divisibility, and residues for repeating conditions. Before choosing an answer, explain why your list or rule is complete. A few successful substitutions show that examples work; they do not show that no other case exists. In the practice questions, make that final completeness statement part of your solution even when the arithmetic is short.

Apply the method to a new case

A club packs identical bags of pencils. The pencil total is divisible by both 12 and 18, is less than 100, and leaves a remainder of 1 when divided by 5. Find the total. Divisibility by both numbers requires a multiple of their least common multiple: 12 = 2²·3 and 18 = 2·3², so the required unit is 36. The positive candidates below 100 are 36 and 72. Only 36 leaves remainder 1 on division by 5. Multiplying 12 by 18 would mistakenly count shared prime factors twice and produce a number beyond the permitted range. For a self-check, divide 36 by each packing size and verify both whole-number quotients; then verify 36 = 5·7 + 1. The final restriction selects among valid multiples rather than changing what divisibility means.

Practice question

Loading saved practice…

In your own words

How would you spot another infer parity from product question, and what would you do first?

Back to the course

Related Resources