Learn the idea. Try it yourself.

Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.

Read the lessonStart practising →

All lessons · Taiwan’s Olympiad route

Your goal: replace a long repeated-digit number by a short remainder process, prove where its repetition begins, and use that proof to settle divisibility and existence questions.

Study plan: two sessions of about 60–75 minutes, with extra time for the final proofs. First complete the diagnostic, examples and nearby tasks. Then attempt the nine written problems, opening hints only when needed. Return another day to any problem completed with help.

Preparation context: original number-theory practice for Taiwan’s APMO preliminary preparation, with proof extensions. The 2027 preliminary brochure specifies five numeric grid-in questions and two written calculation//proof questions in 120 minutes. The short multiple-choice checks on this page are learning checks, not a simulation of that answer format. This lesson is not an official paper or an exact difficulty match.

Prerequisites: quotients and remainders, modular arithmetic, decimal place value, and greatest common divisors. The required recurrence and finite-state arguments are developed here. Problem 8 uses the Euclidean algorithm on indices.

Three starting questions

Try these first. A correct answer matters less than being able to explain the transition.

Diagnostic 1

A positive integer NN has remainder 5 on division by 7. What remainder does the number formed by appending the digit 3 to NN have?

Explanation and prerequisite route

Appending 3 gives 10N+310N + 3, not N+3N + 3. Write N=7q+5N = 7q + 5. Then 10N+3=70q+5310N + 3 = 70q + 53, whose remainder is 4. The large quotient does not matter. If the first step was unclear, revisit place value; if the reduction was unclear, revisit remainders.

Diagnostic 2

We know 3×1≡3×3(mod6)3 \times 1 \equiv 3 \times 3 \pmod{6}. May we cancel 3 and conclude 1≡3(mod6)1 \equiv 3 \pmod{6}?

Explanation and prerequisite route

No. The products 3 and 9 both have remainder 3 modulo 6, but 1 and 3 have different remainders. A factor can be cancelled without changing the modulus only when it is coprime to that modulus. Here gcd⁡(3,6)=3\gcd(3,6) = 3. If this is new, use the cancellation bridge in the pure-cycle section.

Diagnostic 3

Start with remainder 0 and repeatedly apply “multiply by 2, add 1, then reduce modulo 8”. Write the first five remainders, including the starting one. Does the process return to 0?

Explanation and prerequisite route

The remainders are 0,1,3,7,70,1,3,7,7. After reaching 7, the next remainder is again 7 because 2×7+1=15≡7(mod8)2 \times 7 + 1 = 15 \equiv 7 \pmod{8}. It stays 7 forever, so it never returns to 0. A finite process must eventually repeat a state, but the repeated part need not include the starting state. If you assumed the list restarts at 0, keep this example in mind.

Turn place value into a remainder rule

Fix a positive integer modulus mm. Every integer has exactly one remainder in {0,1,…,m−1}\{0,1,\ldots ,m - 1\}. We write A≡B(modm)A \equiv B \pmod{m} when mm divides A−BA - B; equivalently, AA and BB have the same remainder. If two numbers have the same remainder, multiplying both by 10 and adding the same digit preserves that agreement.

Let RnR_{n} be the decimal integer consisting of nn copies of the digit 1, for n≥1n \ge 1. Thus R1=1R_{1} = 1, R2=11R_{2} = 11 and R3=111R_{3} = 111. Set R0=0R_{0} = 0 as a bookkeeping convention for an empty string. The positive numbers RnR_{n} are sometimes called repunits.

Appending another 1 shifts every old digit one place left. Therefore

Rn+1=10Rn+1R_{n+1} = 10R_{n} + 1, with R0=0R_{0} = 0.

If rnr_{n} is the remainder of RnR_{n} modulo mm, then r0=0r_{0} = 0 and rn+1r_{n+1} is the remainder of 10rn+110r_{n} + 1 modulo mm. To justify replacing RnR_{n} by rnr_{n}, write Rn=mq+rnR_{n} = mq + r_{n}. Then 10Rn+1=m(10q)+(10rn+1)10R_{n} + 1 = m(10q) + (10r_{n} + 1). Only the second part affects the new remainder.

More generally, appending a fixed digit dd uses r↦r \mapsto the remainder of 10r+d10r + d. For repeated digits 1≤d≤91 \le d \le 9, the actual nn-digit number is dRndR_{n}. We use the subscript nn for the number of appended digits, and rnr_{n} for the resulting remainder; these are different quantities.

Worked example 1. A very long number, six small states

Find the remainder of R1000R_{1000} on division by 7.

Start at r0=0r_{0} = 0 and apply r↦10r+1r \mapsto 10r + 1 modulo 7:

0→1→4→6→5→2→00 \to 1 \to 4 \to 6 \to 5 \to 2 \to 0.

For example, 10×4+1=4110 \times 4 + 1 = 41 has remainder 6, and 10×2+1=2110 \times 2 + 1 = 21 has remainder 0. Once the state 0 reappears, the same fixed rule produces the same six states again. Thus rn+6=rnr_{n+6} = r_{n} for every n≥0n \ge 0.

Since 1000=6×166+41000 = 6 \times 166 + 4, we need the state at index 4, which is 5. We did not expand a thousand-digit integer. The justification is the repeated state together with the unchanged next-step rule, not merely the appearance of a pattern.

Your turn 1

Find the remainder of R100+R101R_{100} + R_{101} modulo 7.

Compare with a full solution

The indices have remainders 4 and 5 modulo 6. The cycle therefore gives R100≡5R_{100} \equiv 5 and R101≡2(mod7)R_{101} \equiv 2 \pmod{7}. Their sum has remainder 0. We reduce the indices by the cycle length 6, then reduce the resulting sum by the modulus 7; those two moduli serve different purposes.

A finite process has a cycle, possibly after a tail

Suppose a fixed rule sends each of the mm possible remainders to one next remainder. Among the m+1m + 1 states r0,r1,…,rmr_{0},r_{1},\ldots ,r_{m}, two must be equal: there are only mm available values. Say ri=rjr_{i} = r_{j} with i<ji < j. Applying the same rule gives ri+1=rj+1r_{i+1} = r_{j+1}, then ri+2=rj+2r_{i+2} = r_{j+2}, and so on. From index ii onward, the sequence repeats with period j−ij - i.

The states before a repeated cycle are called a tail. A sequence is eventually periodic if it repeats after some starting index. It is purely periodic if a period works from index 0. A repeated state proves future repetition; it does not automatically prove repetition before that state.

When making a table, stop at the first repeated state and record both where it first occurred and the distance between the two occurrences. That identifies the tail length and a cycle. If the rule changes with the step, the same remainder alone may not be enough: for alternating appended digits, record which digit comes next as well, or group the digits into a fixed block.

A tail followed by a fixed state for repunits modulo 8The states 0,1,3,7 occur in order. Arrows lead from 0 to 1, from 1 to 3, from 3 to 7, and from 7 back to itself. The indices of the first visits are 0,1,2,3. The fixed cycle begins at index 3.0137n = 0n = 1n = 2n ≥ 3Each arrow: r ↦ 10r + 1, reduced modulo 8
Original state diagram. The value 7 repeats, while the initial value 0 never returns.

Worked example 2. A genuine tail

Determine the remainder of RnR_{n} modulo 8 for every n≥1n \ge 1. Where does the repeating part begin?

The recurrence gives r0=0r_{0} = 0, r1=1r_{1} = 1, r2=3r_{2} = 3, r3=7r_{3} = 7 and r4=7r_{4} = 7. Since 10×7+1≡7(mod8)10 \times 7 + 1 \equiv 7 \pmod{8}, all later states are 7. Thus the remainder is 1 for n=1n = 1, 3 for n=2n = 2, and 7 for n≥3n \ge 3.

The cycle is the single fixed state 7, and it begins at index 3. It cannot begin earlier: the states at indices 0,1,20,1,2 are 0,1,30,1,3 and none appears again.

Place value gives a second explanation. When n≥3n \ge 3, the final three digits are 111 and every earlier digit contributes a multiple of 1000. Since 8 divides 1000 and 111 has remainder 7, the result follows. This checks both the recurrence and the starting index.

Your turn 2

For the number consisting of nn copies of the digit 6, find its remainder modulo 8 for every n≥1n \ge 1. Is any such positive number divisible by 8?

Compare with a full solution

The rule is now r↦10r+6r \mapsto 10r + 6 modulo 8. Starting at 0 gives 0→6→2→20 \to 6 \to 2 \to 2. Hence the remainder is 6 when n=1n = 1 and 2 when n≥2n \ge 2. The value 2 is fixed because 26≡2(mod8)26 \equiv 2 \pmod{8}. Neither possible positive-index remainder is 0, so no such number is divisible by 8. Changing the appended digit changes the rule; the old table cannot simply be reused unchanged.

Coprimality lets us go backwards

Here is the cancellation fact we need. If gcd⁡(a,m)=1\gcd(a,m) = 1 and mm divides a(u−v)a(u - v), then mm divides u−vu - v. Indeed, no prime dividing mm divides aa; every prime-power factor required by mm must therefore be supplied by u−vu - v. This is the standard prime-factor justification for cancellation, also developed in the gcd lesson.

For integers aa and cc, consider the rule f(r)=f(r) = the remainder of ar+car + c modulo mm. If gcd⁡(a,m)=1\gcd(a,m) = 1 and f(u)=f(v)f(u) = f(v), then mm divides a(u−v)a(u - v), so u≡v(modm)u \equiv v \pmod{m}. Since uu and vv are both between 0 and m−1m - 1, they are equal. Thus different states have different next states. Among mm states this also means every state has exactly one predecessor: the mm distinct images exhaust the mm possible values.

This prevents a tail. Take the first repeated state rj=rir_{j} = r_{i}, with i<ji < j. If ii were positive, unique predecessors would give rj−1=ri−1r_{j-1} = r_{i-1}, a repetition before index jj. That contradicts the choice of the first repeat. Therefore i=0i = 0, and the first repeat returns to the starting state. Every orbit is purely periodic, with a return within mm steps.

For repunits, a=10a = 10 and c=1c = 1. If gcd⁡(10,m)=1\gcd(10,m) = 1, some RLR_{L} with 1≤L≤m1 \le L \le m is divisible by mm. Let LL be the least such positive index. Returning to remainder 0 gives rn+L=rnr_{n + L} = r_{n} for every n≥0n \ge 0. If n=qL+tn = qL + t with 0≤t<L0 \le t < L, then rn=rtr_{n} = r_{t}. By minimality, rtr_{t} is zero only when t=0t = 0. Consequently:

For gcd⁡(10,m)=1\gcd(10,m) = 1, mm divides RnR_{n} exactly when LL divides nn, where LL is the least positive zero-remainder index.

There is no claim that every one of the mm states is visited. For instance, Example 1 visits six states modulo 7 and never visits 3. Also, coprimality is a sufficient condition for every orbit to be purely periodic, not a claim that every non-coprime rule has a tail; starting at a fixed state already gives a cycle.

For a repunit to be divisible by mm at all, mm cannot have a factor 2 or 5, because every positive RnR_{n} ends in 1. Combining this necessity with the preceding proof gives an exact statement: some repunit is divisible by mm if and only if gcd⁡(m,10)=1\gcd(m,10) = 1. For m=1m = 1 the statement is immediate; every RnR_{n} is divisible by 1.

Appending a block changes the multiplier

Fix a decimal block with ℓ\ell digits and value BB, with a nonzero first digit. Let TkT_{k} be the number obtained by repeating the whole block kk times, and set T0=0T_{0} = 0. Appending ℓ\ell digits shifts the old number ℓ\ell places, so

Tk+1=10ℓTk+BT_{k+1} = 10^{\ell}T_{k} + B.

For example, appending the block 37 to 3737 gives 100×3737+37100 \times 3737 + 37. For a three-digit block such as 208, the multiplier is 1000. Internal zeros do not shorten the block. Reduce the multiplier and BB modulo mm first, then follow the finite remainder rule.

Worked example 3. Repeat a two-digit block

Let TkT_{k} be the number formed from kk copies of the block 37. Find the remainder of T2027T_{2027} modulo 13.

The recurrence is Tk+1=100Tk+37T_{k+1} = 100T_{k} + 37. Modulo 13, the multiplier 100 has remainder 9 and the block value 37 has remainder 11. Starting at remainder 0, the rule r↦9r+11r \mapsto 9r + 11 gives

0→11→6→00 \to 11 \to 6 \to 0.

In detail, 9×11+11=1109 \times 11 + 11 = 110 has remainder 6, and 9×6+11=659 \times 6 + 11 = 65 has remainder 0. The cycle therefore has length 3. Since 2027=3×675+22027 = 3 \times 675 + 2, the answer is the state at index 2: 6.

The index counts blocks, so the actual number has 4054 digits. Reducing the number of digits modulo 3 instead of the number of blocks would answer a different recurrence.

Your turn 3

Let UkU_{k} be the number formed from kk copies of the block 208. Find the remainder of U1001U_{1001} modulo 7.

Compare with a full solution

Now Uk+1=1000Uk+208U_{k+1} = 1000U_{k} + 208. Since 1000≡−11000 \equiv -1 and 208≡5(mod7)208 \equiv 5 \pmod{7}, the remainder rule is r↦−r+5r \mapsto -r + 5. Starting at 0 gives 0→5→00 \to 5 \to 0, so even block counts have remainder 0 and odd block counts have remainder 5. Because 1001 is odd, the answer is 5.

The geometric sum does not license modular division

Place value also gives Rn=1+10+⋯+10n−1R_{n} = 1 + 10 + \cdots + 10^{n-1}. Multiplying by 10 and subtracting the original sum cancels all intermediate terms, giving the integer identity 9Rn=10n−19R_{n} = 10^{n} - 1.

It is always valid to divide this integer equality by 9. It is not always valid to divide a congruence modulo mm by 9 while keeping the same modulus. If 9Rn≡0(modm)9R_{n} \equiv 0 \pmod{m} and gcd⁡(9,m)>1\gcd(9,m) > 1, cancellation can lose information. For example, 9R1=99R_{1} = 9 is divisible by 9 but R1=1R_{1} = 1 is not.

The safe equivalent divisibility statement is mm divides RnR_{n} if and only if 9m9m divides 10n−110^{n} - 1. This follows from the integer equality: Rn=mqR_{n} = mq exactly when 10n−1=9mq10^{n} - 1 = 9mq. Often a recurrence or grouped block gives a shorter argument than computing powers modulo 9m9m.

Worked example 4. Divisibility by 27 without dividing aa congruence by 9

Determine every positive integer nn for which 27 divides RnR_{n}.

First reduce modulo 3. Since 10≡1(mod3)10 \equiv 1 \pmod{3}, Rn≡n(mod3)R_{n} \equiv n \pmod{3}. Therefore divisibility by 27 requires n=3qn = 3q for a positive integer qq.

Group the 3q3q ones into qq blocks of 111. Then R3q=111(1+1000+⋯+1000q−1)R_{3q} = 111(1 + 1000 + \cdots + 1000^{q-1}). Modulo 27, we have 1000≡11000 \equiv 1 and 111≡3111 \equiv 3. Therefore R3q≡3q(mod27)R_{3q} \equiv 3q \pmod{27}.

Now 27 divides 3q3q exactly when 9 divides qq: this is ordinary integer divisibility, obtained by writing 3q=27t3q = 27t and dividing the equality by 3. Thus n=3qn = 3q must be a multiple of 27. Conversely, if n=27tn = 27t, then q=9tq = 9t and the same congruence gives Rn≡27t≡0(mod27)R_{n} \equiv 27t \equiv 0 \pmod{27}.

Hence 27 divides RnR_{n} exactly when 27 divides nn. In particular, the least length is 27. Simply noting that 103≡1(mod27)10^{3} \equiv 1 \pmod{27} would not make R3R_{3} divisible by 27: R3=111R_{3} = 111 has remainder 3.

Your turn 4

Find the remainder of R81R_{81} modulo 27, and the remainder of R84R_{84} modulo 27. Explain without writing out the numbers.

Compare with a full solution

Both indices are multiples of 3. Writing 81=3×2781 = 3 \times 27 gives R81≡3×27=81≡R_{81} \equiv 3 \times 27 = 81 \equiv 0 (mod27)\pmod{27}. Writing 84=3×2884 = 3 \times 28 gives R84≡3×28=84≡R_{84} \equiv 3 \times 28 = 84 \equiv 3 (mod27)\pmod{27}. The first is divisible by 27; the second is not. A length divisible by 3 alone is insufficient.

Two identities that help complete proofs

Concatenation and subtraction

Putting a block of ss ones in front of a block of tt ones gives

Rs+t=10tRs+RtR_{s+t} = 10^{t}R_{s} + R_{t}, for s,t≥0s,t \ge 0.

The first block moves tt places to make room for the last tt digits. Equally, for a≥b≥0a \ge b \ge 0, we may split off the first bb ones and write Ra=10a−bRb+Ra−bR_{a} = 10^{a-b}R_{b} + R_{a-b}. These are integer equalities, so they can be used before any reduction.

Another useful difference is Rj−Ri=10iRj−iR_{j} - R_{i} = 10^{i}R_{j-i} for j>i≥0j > i \ge 0: subtracting removes the last ii ones. The result has j−ij - i ones followed by ii zeros. If RjR_{j} and RiR_{i} have equal remainders modulo mm, their difference is divisible by mm. Cancelling 10i10^{i} requires gcd⁡(10,m)=1\gcd(10,m) = 1; keeping the zeros requires no such assumption. Problem 7 exploits that distinction.

Separate a block’s value from its repetition pattern

If A=10ℓA = 10^{\ell}, repeating the block BB gives Tk=BSkT_{k} = B S_{k}, where Sk=1+A+⋯+Ak−1S_{k} = 1 + A + \cdots + A^{k-1}. Let g=gcd⁡(m,B)g = \gcd(m,B), write m=gqm = gq and B=gbB = gb. Then gcd⁡(q,b)=1\gcd(q,b) = 1, because the full common factor was removed. We have mm dividing TkT_{k} exactly when qq divides bSkbS_{k}, and the cancellation fact gives the equivalent condition qq divides SkS_{k}.

This can change an impossible-looking modulus into a manageable one. It does not mean that BB itself can simply be cancelled while leaving mm unchanged. Problem 9 turns this reduction into an existence theorem, including cases where mm has factors 2 or 5.

Nine original written problems

These are original teaching problems using standard mathematical ideas. They are not reproduced, translated or numerically modified official questions. Explain why your cases cover every possibility. Open the two hints in order; the final self-check is an editorial learning rubric, not an official marking scheme.

Build and use the process: Problems 1–2

Problem 1. A remainder condition and a length condition

How many integers nn with 1≤n≤3001 \le n \le 300 satisfy both Rn≡4(mod7)R_{n} \equiv 4 \pmod{7} and n≡2(mod5)n \equiv 2 \pmod{5}?

Hint 1

Use the complete cycle in Example 1 to translate the condition on RnR_{n} into a condition on the index nn.

Hint 2

The first condition is n≡2(mod6)n \equiv 2 \pmod{6}. If n=2+6tn = 2 + 6t, what does the second condition say about tt?

Full solution

The six distinct states in Example 1 show that RnR_{n} has remainder 4 modulo 7 exactly when n≡2(mod6)n \equiv 2 \pmod{6}. Thus n=2+6tn = 2 + 6t with t≥0t \ge 0 in the stated range.

Reducing this expression modulo 5 gives n≡2+t(mod5)n \equiv 2 + t \pmod{5}. Hence n≡2(mod5)n \equiv 2 \pmod{5} exactly when t=5ut = 5u. Therefore all valid lengths have the form n=2+30un = 2 + 30u.

The bound 1≤n≤3001 \le n \le 300 allows u=0,1,…,9u = 0,1,\ldots ,9: the last length is 272, while the next is 302. Every listed length satisfies both original conditions, so the answer is 10.

Check your reasoning

One point each: identify the unique position of remainder 4 in the cycle; derive the combined index condition; check both endpoints; explain that all ten lengths satisfy both original requirements.

Problem 2. Two divisors of a repeated block

Let TkT_{k} be the number formed by repeating the block 26 exactly kk times, where k≥1k \ge 1. Find the least kk for which TkT_{k} is divisible by both 9 and 11, and hence by 99.

Hint 1

Write Tk+1=100Tk+26T_{k+1} = 100T_{k} + 26 and reduce separately modulo 9 and modulo 11.

Hint 2

Modulo 9 the remainder increases by 8 per block; modulo 11 it increases by 4 per block. Use coprime cancellation.

Full solution

Starting at T0=0T_{0} = 0, the recurrence reduces to Tk+1≡Tk+8(mod9)T_{k+1} \equiv T_{k} + 8 \pmod{9}, because 100≡1100 \equiv 1 and 26≡826 \equiv 8. Repeating it gives Tk≡8k(mod9)T_{k} \equiv 8k \pmod{9}. Since gcd⁡(8,9)=1\gcd(8,9) = 1, this is zero exactly when 9 divides kk.

Modulo 11, the same recurrence gives Tk+1≡Tk+4T_{k+1} \equiv T_{k} + 4 and hence Tk≡4kT_{k} \equiv 4k. Since gcd⁡(4,11)=1\gcd(4,11) = 1, this is zero exactly when 11 divides kk.

The positive integers 9 and 11 are coprime, so both divide kk exactly when 99 divides kk. Consequently the least block count is 99, giving a number of 198 digits. For this kk both congruences are zero, so 99 really divides TkT_{k}: its relatively prime factors 9 and 11 both do.

Check your reasoning

One point each: derive both recurrences; justify the cancellations; combine the two length conditions using coprimality; verify the least block count and distinguish 99 blocks from 198 digits.

Choose and justify the model: Problems 3–6

Problem 3. A target the cycle never reaches

Prove that no decimal number consisting of nn copies of the digit 7 followed by the digit 2 is divisible by 13, for any n≥1n \ge 1.

Hint 1

The number is 70Rn+270R_{n} + 2. Work out which remainder of RnR_{n} would be required.

Hint 2

Modulo 13, the repunit cycle from index 0 is 0,1,11,7,6,90,1,11,7,6,9, then 0 again. Check whether the required remainder occurs.

Full solution

The nn copies of 7 form 7Rn7R_{n}; appending 2 gives N=70Rn+2N = 70R_{n} + 2. Modulo 13, this is 5Rn+25R_{n} + 2. If it were zero, then 5Rn≡11(mod13)5R_{n} \equiv 11 \pmod{13}. Multiplication by 8 is valid because 5×8≡1(mod13)5 \times 8 \equiv 1 \pmod{13}, giving Rn≡88≡10(mod13)R_{n} \equiv 88 \equiv 10 \pmod{13}.

Now compute the whole orbit from 0 using r↦10r+1r \mapsto 10r + 1 modulo 13: 0→1→11→7→6→9→00 \to 1 \to 11 \to 7 \to 6 \to 9 \to 0. The next state after 9 is 91≡091 \equiv 0, so the cycle repeats forever. The value 10 does not occur.

Therefore the necessary remainder cannot be reached and no positive nn works. The map is invertible modulo 13, but its orbit from 0 contains only six of the thirteen states. Invertibility does not force a particular orbit to visit every state.

Check your reasoning

One point each: encode the entire number correctly; find the required residue with a justified inverse; close and verify the complete reachable cycle; use its missing target to exclude every positive length.

Problem 4. A remainder that occurs only in the tail

Determine all positive integers nn for which RnR_{n} has remainder 1 or remainder 3 modulo 12. Also find the least nonnegative index NN for which rn+3=rnr_{n+3} = r_{n} for every n≥Nn \ge N, where rnr_{n} is the remainder of RnR_{n} modulo 12.

Hint 1

Compute from r0=0r_{0} = 0 until a state repeats. Record the first index of that repeated state.

Hint 2

The list begins 0,1,11,3,7,110,1,11,3,7,11. The repeated state is 11, not 0. Separate the isolated value 1 from the recurring value 3.

Full solution

The rule r↦10r+1r \mapsto 10r + 1 modulo 12 gives 0→1→11→3→7→110 \to 1 \to 11 \to 3 \to 7 \to 11. Since the state at index 5 equals that at index 2, the three-state cycle 11,3,711,3,7 repeats from index 2 onward.

Remainder 1 occurs at n=1n = 1 and never in the cycle, so it occurs only once. Remainder 3 first occurs at n=3n = 3 and then every three steps: exactly n=3,6,9,…n = 3,6,9,\ldots . Thus the requested positive lengths are n=1n = 1 and all positive multiples of 3.

The equality rn+3=rnr_{n+3} = r_{n} holds for every n≥2n \ge 2. It does not hold at n=1n = 1, since r1=1r_{1} = 1 and r4=7r_{4} = 7. It also fails at n=0n = 0, since r0=0r_{0} = 0 and r3=3r_{3} = 3. Therefore the least allowed starting index is N=2N = 2.

Check your reasoning

One point each: identify the first repeat and its earlier index; separate transient and recurring remainders; give every requested positive length; prove both that N=2N = 2 works and that no smaller NN works.

Problem 5. One modulus gives alternation, another gives accumulation

Let TkT_{k} be the decimal number formed by repeating the block 202 exactly kk times. Find the least positive kk for which 259 divides TkT_{k}.

Hint 1

Factor 259 as 7×377 \times 37. Use the multiplier 1000, not 10 or 100.

Hint 2

Modulo 7 the update is r↦−r+6r \mapsto -r + 6; modulo 37 it is r↦r+17r \mapsto r + 17. Find the zero indices for both processes.

Full solution

The recurrence is Tk+1=1000Tk+202T_{k+1} = 1000T_{k} + 202. Modulo 7, we have 1000≡−11000 \equiv -1 and 202≡6202 \equiv 6, giving the cycle 0→6→00 \to 6 \to 0. Thus 7 divides TkT_{k} exactly when kk is even.

Modulo 37, 1000≡11000 \equiv 1 because 999=27×37999 = 27 \times 37, and 202≡17202 \equiv 17. Starting at 0 gives Tk≡17k(mod37)T_{k} \equiv 17k \pmod{37}. Since gcd⁡(17,37)=1\gcd(17,37) = 1, this is zero exactly when 37 divides kk.

Both requirements hold exactly when kk is a positive multiple of 74. Because 7 and 37 are coprime, their simultaneous divisibility is equivalent to divisibility by 259. Hence the least kk is 74. The resulting number has 3×74=2223 \times 74 = 222 digits, but its divisibility has been proved without expanding it.

Check your reasoning

One point each: use the correct block multiplier; prove the parity condition modulo 7; prove the length condition modulo 37; combine necessity and sufficiency to establish the least value 74.

Problem 6. The index supplies part of the divisor

Determine all positive integers nn such that 27 divides nRnnR_{n}.

Hint 1

First reduce nRnnR_{n} modulo 3. Recall that Rn≡n(mod3)R_{n} \equiv n \pmod{3}.

Hint 2

After proving n=3qn = 3q, use R3q≡3q(mod27)R_{3q} \equiv 3q \pmod{27} from Example 4. What condition on qq makes 9q29q^{2} divisible by 27?

Full solution

Modulo 3, nRn≡n2nR_{n} \equiv n^{2}. If 27 divides nRnnR_{n}, then 3 divides n2n^{2}. The remainders 1 and 2 both have square remainder 1 modulo 3, so this forces 3 to divide nn. Write n=3qn = 3q.

Grouping the ones into blocks of 111, as in Example 4, gives R3q≡3q(mod27)R_{3q} \equiv 3q \pmod{27}. Multiplying by n=3qn = 3q yields nRn≡9q2(mod27)nR_{n} \equiv 9q^{2} \pmod{27}. Now 27 divides 9q29q^{2} exactly when 3 divides q2q^{2}, and the same square-remainder check shows that this is equivalent to 3 dividing qq.

Thus a necessary condition is n=9tn = 9t. Conversely, for n=9tn = 9t we have q=3tq = 3t and 9q2=81t29q^{2} = 81t^{2}, which is divisible by 27; the congruence then gives 27 dividing nRnnR_{n}. Therefore the complete answer is all positive multiples of 9.

For instance n=9n = 9 works even though R9R_{9} itself is not divisible by 27. In a product, the required factors can be shared between its two factors.

Check your reasoning

One point each: derive the first divisibility by 3; apply the grouped congruence only after n=3qn = 3q is known; reduce the product condition correctly; prove the converse for every positive multiple of 9.

Build complete arguments: Problems 7–9

Problem 7. Zeros remove the coprimality obstacle

Prove that for every positive integer mm there is a positive multiple of mm whose decimal digits are all 0 or 1 and whose number of digits is at most mm. Then use the remainder table modulo 12 from Problem 4 to construct one such multiple of 12.

Hint 1

Consider R1,R2,…,RmR_{1},R_{2},\ldots ,R_{m}. If none has remainder 0, how many nonzero remainder values are available?

Hint 2

Two equal remainders give a divisible difference Rj−RiR_{j} - R_{i}. Keep the trailing zeros in that difference; do not cancel a power of 10.

Full solution

Consider the mm positive repunits R1,…,RmR_{1},\ldots ,R_{m}. If any is divisible by mm, it already has only the digit 1 and at most mm digits, so we are done. This includes m=1m = 1, since R1=1R_{1} = 1.

Otherwise all mm remainders lie among the m−1m - 1 nonzero values 1,…,m−11,\ldots ,m - 1. At least two must agree: choose 1≤i<j≤m1 \le i < j \le m with Ri≡Rj(modm)R_{i} \equiv R_{j} \pmod{m}. Therefore mm divides Rj−RiR_{j} - R_{i}.

The difference equals 10iRj−i10^{i}R_{j-i}. In decimal it has j−ij - i copies of 1 followed by ii copies of 0. It is positive, has only the permitted digits, and has exactly j≤mj \le m digits. No factor has been cancelled modulo mm, so no coprimality assumption is needed.

Modulo 12, the table gives R2R_{2} and R5R_{5} the same remainder 11. Their difference is 11111−11=11111 - 11 = 11100, and 11100=12×92511100 = 12 \times 925. This is a positive five-digit example. The proof guarantees at most mm digits, not necessarily the shortest possible multiple.

Check your reasoning

Five points: use exactly mm repunits; handle a zero remainder separately; justify a repeated nonzero remainder otherwise; prove the difference is positive and has the required digits and length; give and verify the concrete multiple of 12 without illicit cancellation.

Problem 8. The Euclidean algorithm acts on the indices

For positive integers aa and bb, prove gcd⁡(Ra,Rb)=Rg\gcd(R_{a},R_{b}) = R_{g}, where g=gcd⁡(a,b)g = \gcd(a,b). Deduce that RaR_{a} divides RbR_{b} if and only if aa divides bb, and evaluate gcd⁡(R84,R126)\gcd(R_{84},R_{126}).

Hint 1

For a≥ba \ge b, use Ra=10a−bRb+Ra−bR_{a} = 10^{a-b}R_{b} + R_{a-b}. Subtracting a multiple of one number does not change the gcd.

Hint 2

The gcd of the repunits reduces from indices (a,b)(a,b) to (b,a−b)(b,a - b). Apply repeated subtraction, as in the Euclidean algorithm, until one index is 0.

Full solution

For a≥ba \ge b, concatenation gives Ra=10a−bRb+Ra−bR_{a} = 10^{a-b}R_{b} + R_{a-b}. A number divides both RaR_{a} and RbR_{b} exactly when it divides both RbR_{b} and Ra−bR_{a-b}, because each pair is obtained from the other by adding or subtracting that multiple. Therefore gcd⁡(Ra,Rb)=gcd⁡(Rb,Ra−b)\gcd(R_{a},R_{b}) = \gcd(R_{b},R_{a-b}).

The same operation preserves gcd⁡(a,b)\gcd(a,b) on the indices. If necessary interchange the indices so that the larger is first. Repeatedly subtracting the smaller positive index decreases their sum, so the process eventually reaches (g,0)(g,0), with g=gcd⁡(a,b)g = \gcd(a,b). Applying the corresponding repunit equality at every step gives gcd⁡(Ra,Rb)=gcd⁡(Rg,R0)\gcd(R_{a},R_{b}) = \gcd(R_{g},R_{0}). Since R0=0R_{0} = 0, this last gcd is RgR_{g}.

Now RaR_{a} divides RbR_{b} exactly when their gcd equals RaR_{a}. By the proved identity, that means Rg=RaR_{g} = R_{a}. The positive repunits strictly increase with their index, since Rn+1=10Rn+1>RnR_{n+1} = 10R_{n} + 1 > R_{n}. Hence Rg=RaR_{g} = R_{a} exactly when g=ag = a, which is equivalent to aa dividing bb.

Finally gcd⁡(84,126)=42\gcd(84,126) = 42, so gcd⁡(R84,R126)=R42\gcd(R_{84},R_{126}) = R_{42}, the number consisting of 42 ones. This argument establishes the exact gcd rather than merely finding one common divisor.

Check your reasoning

Five points: derive the concatenation identity; prove the gcd-preserving step; justify termination and the final index gcd; use R0=0R_{0} = 0 correctly; prove both directions of the divisibility consequence and compute the 42-digit gcd.

Problem 9. Exactly when can a repeated block be divisible?

Fix a decimal block of length ℓ≥1\ell \ge 1 and positive value BB, with a nonzero first digit. Let TkT_{k} be the number formed by kk copies of this block. For a positive integer mm, put q=m/gcd⁡(m,B)q = m/\gcd(m,B). Prove that some TkT_{k} with k≥1k \ge 1 is divisible by mm if and only if gcd⁡(q,10)=1\gcd(q,10) = 1. When such a kk exists, prove that the working block counts are exactly the positive multiples of a least L≤qL \le q. Apply this to blocks 12 and 24 with modulus 72.

Hint 1

Factor TkT_{k} as BB times 1+10ℓ+⋯+10(k−1)ℓ1 + 10^{\ell} + \cdots + 10^{(k-1)\ell}, and first remove gcd⁡(m,B)\gcd(m,B) from the divisibility condition.

Hint 2

If the reduced modulus has a factor 2 or 5, the geometric sum has remainder 1 modulo that prime. Otherwise its append rule is invertible, so use a first return to 0 and minimality.

Full solution

Let A=10ℓA = 10^{\ell}, let g=gcd⁡(m,B)g = \gcd(m,B), and write m=gqm = gq and B=gbB = gb. Then gcd⁡(q,b)=1\gcd(q,b) = 1. For k≥1k \ge 1, the repeated-block number is Tk=BSkT_{k} = B S_{k}, where Sk=1+A+⋯+Ak−1S_{k} = 1 + A + \cdots + A^{k-1}. Thus mm divides TkT_{k} exactly when qq divides bSkbS_{k}, which by coprime cancellation is equivalent to qq dividing SkS_{k}.

Necessity. If a prime pp equal to 2 or 5 divides qq, then AA is divisible by pp. Every term of SkS_{k} except its initial 1 is divisible by pp, so Sk≡1(modp)S_{k} \equiv 1 \pmod{p}. It cannot be divisible by qq. Therefore existence requires gcd⁡(q,10)=1\gcd(q,10) = 1.

Sufficiency. Suppose gcd⁡(q,10)=1\gcd(q,10) = 1. Then gcd⁡(A,q)=1\gcd(A,q) = 1 as well. Starting from S0=0S_{0} = 0, the recurrence Sk+1=ASk+1S_{k+1} = AS_{k} + 1 gives an invertible remainder map modulo qq. The pure-cycle proof shows that it returns to remainder 0 within qq steps. Hence a least positive return index LL exists with 1≤L≤q1 \le L \le q, and TLT_{L} is divisible by mm. This includes q=1q = 1, when every remainder is 0 and L=1L = 1.

From the return to 0, the same rule gives Sn+L≡Sn(modq)S_{n + L} \equiv S_{n} \pmod{q} for all n≥0n \ge 0. Write k=tL+rk = tL + r with 0≤r<L0 \le r < L. Then Sk≡SrS_{k} \equiv S_{r}, and by minimality of LL this is zero exactly when r=0r = 0. Therefore mm divides TkT_{k} exactly when LL divides kk.

For block 12 and m=72m = 72, the reduced modulus is q=72/gcd⁡(72,12)=6q = 72/\gcd(72,12) = 6, which shares a factor 2 with 10. No positive block count works. For block 24 and m=72m = 72, q=72/24=3q = 72/24 = 3. Since A=100≡1(mod3)A = 100 \equiv 1 \pmod{3}, we have Sk≡k(mod3)S_{k} \equiv k \pmod{3}, so the least block count is 3. Indeed 242424=72×3367242424 = 72 \times 3367. The same modulus can reject one block and accept another because the block value supplies different common factors.

Check your reasoning

Five points: reduce to qq dividing the geometric sum with justified cancellation; prove the obstruction from 2 or 5; prove a return to 0 within qq steps; derive all working indices from the least return; treat q=1q = 1 and verify both block applications.

Nine short adaptive checks

The engine chooses six responses from the nine available checks for a practice session. Completing that session records completion, not mastery or a proof assessment. Use the hints and explanations to locate a specific gap, then return to the written tasks. These learning checks use multiple choice; Taiwan’s verified preliminary includes numeric grid-in and written work. All content is free without mandatory sign-in.

Interactive practice loads here. You can also use the complete question set below.

Exit task: necessity and sufficiency

Close Problem 9’s solution. Explain why removing gcd⁡(m,B)\gcd(m,B) is the correct first step, why factors 2 and 5 obstruct the reduced geometric sum, and why an invertible finite remainder process must return to its starting state. Finish by proving that every successful block count is a multiple of the least one.

Planning hint

An “if and only if” statement needs both directions. For necessity, reduce the sum modulo a prime divisor 2 or 5. For sufficiency, identify the multiplier and its coprimality. For completeness, divide the index by the least return time and use its remainder.

Compare with a full proof

Let A=10ℓA = 10^{\ell}, let g=gcd⁡(m,B)g = \gcd(m,B), and write m=gqm = gq and B=gbB = gb. Then gcd⁡(q,b)=1\gcd(q,b) = 1. For k≥1k \ge 1, the repeated-block number is Tk=BSkT_{k} = B S_{k}, where Sk=1+A+⋯+Ak−1S_{k} = 1 + A + \cdots + A^{k-1}. Thus mm divides TkT_{k} exactly when qq divides bSkbS_{k}, which by coprime cancellation is equivalent to qq dividing SkS_{k}.

Necessity. If a prime pp equal to 2 or 5 divides qq, then AA is divisible by pp. Every term of SkS_{k} except its initial 1 is divisible by pp, so Sk≡1(modp)S_{k} \equiv 1 \pmod{p}. It cannot be divisible by qq. Therefore existence requires gcd⁡(q,10)=1\gcd(q,10) = 1.

Sufficiency. Suppose gcd⁡(q,10)=1\gcd(q,10) = 1. Then gcd⁡(A,q)=1\gcd(A,q) = 1 as well. Starting from S0=0S_{0} = 0, the recurrence Sk+1=ASk+1S_{k+1} = AS_{k} + 1 gives an invertible remainder map modulo qq. The pure-cycle proof shows that it returns to remainder 0 within qq steps. Hence a least positive return index LL exists with 1≤L≤q1 \le L \le q, and TLT_{L} is divisible by mm. This includes q=1q = 1, when every remainder is 0 and L=1L = 1.

From the return to 0, the same rule gives Sn+L≡Sn(modq)S_{n + L} \equiv S_{n} \pmod{q} for all n≥0n \ge 0. Write k=tL+rk = tL + r with 0≤r<L0 \le r < L. Then Sk≡SrS_{k} \equiv S_{r}, and by minimality of LL this is zero exactly when r=0r = 0. Therefore mm divides TkT_{k} exactly when LL divides kk.

For block 12 and m=72m = 72, the reduced modulus is q=72/gcd⁡(72,12)=6q = 72/\gcd(72,12) = 6, which shares a factor 2 with 10. No positive block count works. For block 24 and m=72m = 72, q=72/24=3q = 72/24 = 3. Since A=100≡1(mod3)A = 100 \equiv 1 \pmod{3}, we have Sk≡k(mod3)S_{k} \equiv k \pmod{3}, so the least block count is 3. Indeed 242424=72×3367242424 = 72 \times 3367. The same modulus can reject one block and accept another because the block value supplies different common factors.

A remainder-proof checklist

This is a self-review guide, not an official marking scheme. Award one point for each item you can identify in your written argument.

  1. Encoding: I define the number, its digit or block count, its starting index and its correct append multiplier.
  2. State rule: I show why the old remainder determines the next remainder under this fixed rule.
  3. Period: I identify a repeated state and its earlier index, then explain whether a tail exists. I do not reduce all indices modulo a cycle length without checking its start.
  4. Divisibility: every cancelled factor is coprime to the unchanged modulus, or I explicitly adjust the modulus using integer divisibility.
  5. Completeness: I justify “all”, “least” or “if and only if”, including boundary cases and a construction when existence is claimed.

My proof notebook

Write on paper or use the optional browser notebook. It stores your own working when you choose to enable storage; it does not automatically mark proofs.

Choose your next step

Contest context and originality

The official 2027 preliminary notice and linked brochure establish the stated preparation context. The released 2026 preliminary paper includes repeated-digit remainder reasoning, supporting this editorial topic choice. It is linked for official practice, not reproduced here. These explanations, examples, problems and diagram are original AI-assisted teaching material using standard mathematics. No affiliation, endorsement, exact difficulty equivalence or prediction of future questions is claimed. Sources checked 19 October 2026.

Prepared for IMOolympiad.com. Report a specific unclear step or correction. Optional progress stays in this browser.