Divisibility is the habit of tracking when one integer divides another through factors, residues, and prime powers. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
The positive divisors of $2$ are $1$ and $2$, so $n + 1 \in \{1, 2\}$, giving $n = 0$ or $n = 1$; only $n = 1$ is positive.
4
Check: $n = 1$ gives $n + 1 = 2$ and $n^2 + 1 = 2$, and $2 \mid 2$.
Answer:
$n = 1$
Contest level
Find all positive integers $n$ for which $(2n - 1) \mid (n^2 + n)$.
1
Since $\gcd(2n-1, 2) = 1$, divisibility by $2n - 1$ is unaffected by multiplying the dividend by $2$ (or $4$). Scale to clear fractions: consider $4(n^2 + n) = 4n^2 + 4n$.
Thus $(2n-1) \mid 4(n^2+n)$ iff $(2n-1) \mid 3$, and because $\gcd(2n-1,4)=1$ this is equivalent to $(2n-1) \mid (n^2+n)$.
4
Positive odd divisors of $3$ are $1$ and $3$: $2n - 1 = 1 \Rightarrow n = 1$, and $2n - 1 = 3 \Rightarrow n = 2$. Check: $n=1$ gives $1 \mid 2$; $n=2$ gives $3 \mid 6$.
Answer:
$n \in \{1, 2\}$
Olympiad / Challenge
Find all positive integers $n$ such that $n \mid (2^n - 1)$.
1
Clearly $n = 1$ works ($1 \mid 1$). Suppose $n > 1$ is a solution and let $p$ be the smallest prime factor of $n$.
2
Then $2^n \equiv 1 \pmod p$, so the order $d = \operatorname{ord}_p(2)$ divides $n$. Also $d \mid (p - 1)$ by Fermat, so $d \mid \gcd(n, p-1)$.
3
Every prime factor of $p - 1$ is smaller than $p$, hence cannot divide $n$ (as $p$ is the smallest prime factor of $n$), so $\gcd(n, p-1) = 1$. Therefore $d \mid 1$, i.e. $d = 1$.
4
But $d = 1$ means $2^1 \equiv 1 \pmod p$, i.e. $p \mid 1$, impossible. So no $n > 1$ works.
Answer:
$n = 1$ is the only solution.
Going Deeper
Generalization: the core trick is that $d \mid a$ and $d \mid b$ imply $d \mid (ax + by)$. To test whether $(n + c) \mid f(n)$ for a polynomial $f$, reduce $f$ modulo $n + c$ by substituting $n \equiv -c$; the divisibility reduces to whether $n + c$ divides the constant $f(-c)$.
Where it appears: 'find all $n$ such that $A(n) \mid B(n)$' problems, simplifying that $\frac{B(n)}{A(n)}$ is an integer for finitely many $n$, and the polynomial-remainder step that turns an unbounded search into a finite divisor check.
Pitfall: when you multiply the dividend by a constant $k$ to clear a fraction (as in the $2n-1$ example), you must ensure $\gcd(k, \text{divisor}) = 1$, or you can introduce spurious solutions. Multiplying $n^2+n$ by $4$ was safe only because $\gcd(4, 2n-1) = 1$.
Spot the Signal
Look for problems where the key step is tracking when one integer divides another through factors, residues, and prime powers.
You can describe the hard part as tracking when one integer divides another through factors, residues, and prime powers, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the integer constraint that calls for divisibility, then rewrite the givens around it.
Name the relation that makes Divisibility legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Divisibility just because the surface looks familiar; verify the required condition first.
Applying Divisibility because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let divisibility reveal the integer structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is tracking when one integer divides another through factors, residues, and prime powers.