Learn the idea. Try it yourself.
Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.
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 calculationproof 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 has remainder 5 on division by 7. What remainder does the number formed by appending the digit 3 to have?
Explanation and prerequisite route
Appending 3 gives , not . Write . Then , 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 . May we cancel 3 and conclude ?
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 . 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 . After reaching 7, the next remainder is again 7 because . 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 . Every integer has exactly one remainder in . We write when divides ; equivalently, and have the same remainder. If two numbers have the same remainder, multiplying both by 10 and adding the same digit preserves that agreement.
Let be the decimal integer consisting of copies of the digit 1, for . Thus , and . Set as a bookkeeping convention for an empty string. The positive numbers are sometimes called repunits.
Appending another 1 shifts every old digit one place left. Therefore
, with .
If is the remainder of modulo , then and is the remainder of modulo . To justify replacing by , write . Then . Only the second part affects the new remainder.
More generally, appending a fixed digit uses the remainder of . For repeated digits , the actual -digit number is . We use the subscript for the number of appended digits, and for the resulting remainder; these are different quantities.
Worked example 1. A very long number, six small states
Find the remainder of on division by 7.
Start at and apply modulo 7:
.
For example, has remainder 6, and has remainder 0. Once the state 0 reappears, the same fixed rule produces the same six states again. Thus for every .
Since , 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 modulo 7.
Compare with a full solution
The indices have remainders 4 and 5 modulo 6. The cycle therefore gives and . 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 possible remainders to one next remainder. Among the states , two must be equal: there are only available values. Say with . Applying the same rule gives , then , and so on. From index onward, the sequence repeats with period .
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.
Worked example 2. A genuine tail
Determine the remainder of modulo 8 for every . Where does the repeating part begin?
The recurrence gives , , , and . Since , all later states are 7. Thus the remainder is 1 for , 3 for , and 7 for .
The cycle is the single fixed state 7, and it begins at index 3. It cannot begin earlier: the states at indices are and none appears again.
Place value gives a second explanation. When , 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 copies of the digit 6, find its remainder modulo 8 for every . Is any such positive number divisible by 8?
Compare with a full solution
The rule is now modulo 8. Starting at 0 gives . Hence the remainder is 6 when and 2 when . The value 2 is fixed because . 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 and divides , then divides . Indeed, no prime dividing divides ; every prime-power factor required by must therefore be supplied by . This is the standard prime-factor justification for cancellation, also developed in the gcd lesson.
For integers and , consider the rule the remainder of modulo . If and , then divides , so . Since and are both between 0 and , they are equal. Thus different states have different next states. Among states this also means every state has exactly one predecessor: the distinct images exhaust the possible values.
This prevents a tail. Take the first repeated state , with . If were positive, unique predecessors would give , a repetition before index . That contradicts the choice of the first repeat. Therefore , and the first repeat returns to the starting state. Every orbit is purely periodic, with a return within steps.
For repunits, and . If , some with is divisible by . Let be the least such positive index. Returning to remainder 0 gives for every . If with , then . By minimality, is zero only when . Consequently:
For , divides exactly when divides , where is the least positive zero-remainder index.
There is no claim that every one of the 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 at all, cannot have a factor 2 or 5, because every positive ends in 1. Combining this necessity with the preceding proof gives an exact statement: some repunit is divisible by if and only if . For the statement is immediate; every is divisible by 1.
Appending a block changes the multiplier
Fix a decimal block with digits and value , with a nonzero first digit. Let be the number obtained by repeating the whole block times, and set . Appending digits shifts the old number places, so
.
For example, appending the block 37 to 3737 gives . For a three-digit block such as 208, the multiplier is 1000. Internal zeros do not shorten the block. Reduce the multiplier and modulo first, then follow the finite remainder rule.
Worked example 3. Repeat a two-digit block
Let be the number formed from copies of the block 37. Find the remainder of modulo 13.
The recurrence is . Modulo 13, the multiplier 100 has remainder 9 and the block value 37 has remainder 11. Starting at remainder 0, the rule gives
.
In detail, has remainder 6, and has remainder 0. The cycle therefore has length 3. Since , 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 be the number formed from copies of the block 208. Find the remainder of modulo 7.
Compare with a full solution
Now . Since and , the remainder rule is . Starting at 0 gives , 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 . Multiplying by 10 and subtracting the original sum cancels all intermediate terms, giving the integer identity .
It is always valid to divide this integer equality by 9. It is not always valid to divide a congruence modulo by 9 while keeping the same modulus. If and , cancellation can lose information. For example, is divisible by 9 but is not.
The safe equivalent divisibility statement is divides if and only if divides . This follows from the integer equality: exactly when . Often a recurrence or grouped block gives a shorter argument than computing powers modulo .
Worked example 4. Divisibility by 27 without dividing congruence by 9
Determine every positive integer for which 27 divides .
First reduce modulo 3. Since , . Therefore divisibility by 27 requires for a positive integer .
Group the ones into blocks of 111. Then . Modulo 27, we have and . Therefore .
Now 27 divides exactly when 9 divides : this is ordinary integer divisibility, obtained by writing and dividing the equality by 3. Thus must be a multiple of 27. Conversely, if , then and the same congruence gives .
Hence 27 divides exactly when 27 divides . In particular, the least length is 27. Simply noting that would not make divisible by 27: has remainder 3.
Your turn 4
Find the remainder of modulo 27, and the remainder of modulo 27. Explain without writing out the numbers.
Compare with a full solution
Both indices are multiples of 3. Writing gives 0 . Writing gives 3 . 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 ones in front of a block of ones gives
, for .
The first block moves places to make room for the last digits. Equally, for , we may split off the first ones and write . These are integer equalities, so they can be used before any reduction.
Another useful difference is for : subtracting removes the last ones. The result has ones followed by zeros. If and have equal remainders modulo , their difference is divisible by . Cancelling requires ; keeping the zeros requires no such assumption. Problem 7 exploits that distinction.
Separate a block’s value from its repetition pattern
If , repeating the block gives , where . Let , write and . Then , because the full common factor was removed. We have dividing exactly when divides , and the cancellation fact gives the equivalent condition divides .
This can change an impossible-looking modulus into a manageable one. It does not mean that itself can simply be cancelled while leaving unchanged. Problem 9 turns this reduction into an existence theorem, including cases where 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 with satisfy both and ?
Hint 1
Use the complete cycle in Example 1 to translate the condition on into a condition on the index .
Hint 2
The first condition is . If , what does the second condition say about ?
Full solution
The six distinct states in Example 1 show that has remainder 4 modulo 7 exactly when . Thus with in the stated range.
Reducing this expression modulo 5 gives . Hence exactly when . Therefore all valid lengths have the form .
The bound allows : 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 be the number formed by repeating the block 26 exactly times, where . Find the least for which is divisible by both 9 and 11, and hence by 99.
Hint 1
Write 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 , the recurrence reduces to , because and . Repeating it gives . Since , this is zero exactly when 9 divides .
Modulo 11, the same recurrence gives and hence . Since , this is zero exactly when 11 divides .
The positive integers 9 and 11 are coprime, so both divide exactly when 99 divides . Consequently the least block count is 99, giving a number of 198 digits. For this both congruences are zero, so 99 really divides : 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 copies of the digit 7 followed by the digit 2 is divisible by 13, for any .
Hint 1
The number is . Work out which remainder of would be required.
Hint 2
Modulo 13, the repunit cycle from index 0 is , then 0 again. Check whether the required remainder occurs.
Full solution
The copies of 7 form ; appending 2 gives . Modulo 13, this is . If it were zero, then . Multiplication by 8 is valid because , giving .
Now compute the whole orbit from 0 using modulo 13: . The next state after 9 is , so the cycle repeats forever. The value 10 does not occur.
Therefore the necessary remainder cannot be reached and no positive 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 for which has remainder 1 or remainder 3 modulo 12. Also find the least nonnegative index for which for every , where is the remainder of modulo 12.
Hint 1
Compute from until a state repeats. Record the first index of that repeated state.
Hint 2
The list begins . The repeated state is 11, not 0. Separate the isolated value 1 from the recurring value 3.
Full solution
The rule modulo 12 gives . Since the state at index 5 equals that at index 2, the three-state cycle repeats from index 2 onward.
Remainder 1 occurs at and never in the cycle, so it occurs only once. Remainder 3 first occurs at and then every three steps: exactly . Thus the requested positive lengths are and all positive multiples of 3.
The equality holds for every . It does not hold at , since and . It also fails at , since and . Therefore the least allowed starting index is .
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 works and that no smaller works.
Problem 5. One modulus gives alternation, another gives accumulation
Let be the decimal number formed by repeating the block 202 exactly times. Find the least positive for which 259 divides .
Hint 1
Factor 259 as . Use the multiplier 1000, not 10 or 100.
Hint 2
Modulo 7 the update is ; modulo 37 it is . Find the zero indices for both processes.
Full solution
The recurrence is . Modulo 7, we have and , giving the cycle . Thus 7 divides exactly when is even.
Modulo 37, because , and . Starting at 0 gives . Since , this is zero exactly when 37 divides .
Both requirements hold exactly when is a positive multiple of 74. Because 7 and 37 are coprime, their simultaneous divisibility is equivalent to divisibility by 259. Hence the least is 74. The resulting number has 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 such that 27 divides .
Hint 1
First reduce modulo 3. Recall that .
Hint 2
After proving , use from Example 4. What condition on makes divisible by 27?
Full solution
Modulo 3, . If 27 divides , then 3 divides . The remainders 1 and 2 both have square remainder 1 modulo 3, so this forces 3 to divide . Write .
Grouping the ones into blocks of 111, as in Example 4, gives . Multiplying by yields . Now 27 divides exactly when 3 divides , and the same square-remainder check shows that this is equivalent to 3 dividing .
Thus a necessary condition is . Conversely, for we have and , which is divisible by 27; the congruence then gives 27 dividing . Therefore the complete answer is all positive multiples of 9.
For instance works even though 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 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 there is a positive multiple of whose decimal digits are all 0 or 1 and whose number of digits is at most . Then use the remainder table modulo 12 from Problem 4 to construct one such multiple of 12.
Hint 1
Consider . If none has remainder 0, how many nonzero remainder values are available?
Hint 2
Two equal remainders give a divisible difference . Keep the trailing zeros in that difference; do not cancel a power of 10.
Full solution
Consider the positive repunits . If any is divisible by , it already has only the digit 1 and at most digits, so we are done. This includes , since .
Otherwise all remainders lie among the nonzero values . At least two must agree: choose with . Therefore divides .
The difference equals . In decimal it has copies of 1 followed by copies of 0. It is positive, has only the permitted digits, and has exactly digits. No factor has been cancelled modulo , so no coprimality assumption is needed.
Modulo 12, the table gives and the same remainder 11. Their difference is 11100, and . This is a positive five-digit example. The proof guarantees at most digits, not necessarily the shortest possible multiple.
Check your reasoning
Five points: use exactly 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 and , prove , where . Deduce that divides if and only if divides , and evaluate .
Hint 1
For , use . Subtracting a multiple of one number does not change the gcd.
Hint 2
The gcd of the repunits reduces from indices to . Apply repeated subtraction, as in the Euclidean algorithm, until one index is 0.
Full solution
For , concatenation gives . A number divides both and exactly when it divides both and , because each pair is obtained from the other by adding or subtracting that multiple. Therefore .
The same operation preserves 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 , with . Applying the corresponding repunit equality at every step gives . Since , this last gcd is .
Now divides exactly when their gcd equals . By the proved identity, that means . The positive repunits strictly increase with their index, since . Hence exactly when , which is equivalent to dividing .
Finally , so , 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 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 and positive value , with a nonzero first digit. Let be the number formed by copies of this block. For a positive integer , put . Prove that some with is divisible by if and only if . When such a exists, prove that the working block counts are exactly the positive multiples of a least . Apply this to blocks 12 and 24 with modulus 72.
Hint 1
Factor as times , and first remove 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 , let , and write and . Then . For , the repeated-block number is , where . Thus divides exactly when divides , which by coprime cancellation is equivalent to dividing .
Necessity. If a prime equal to 2 or 5 divides , then is divisible by . Every term of except its initial 1 is divisible by , so . It cannot be divisible by . Therefore existence requires .
Sufficiency. Suppose . Then as well. Starting from , the recurrence gives an invertible remainder map modulo . The pure-cycle proof shows that it returns to remainder 0 within steps. Hence a least positive return index exists with , and is divisible by . This includes , when every remainder is 0 and .
From the return to 0, the same rule gives for all . Write with . Then , and by minimality of this is zero exactly when . Therefore divides exactly when divides .
For block 12 and , the reduced modulus is , which shares a factor 2 with 10. No positive block count works. For block 24 and , . Since , we have , so the least block count is 3. Indeed . 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 dividing the geometric sum with justified cancellation; prove the obstruction from 2 or 5; prove a return to 0 within steps; derive all working indices from the least return; treat 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 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 , let , and write and . Then . For , the repeated-block number is , where . Thus divides exactly when divides , which by coprime cancellation is equivalent to dividing .
Necessity. If a prime equal to 2 or 5 divides , then is divisible by . Every term of except its initial 1 is divisible by , so . It cannot be divisible by . Therefore existence requires .
Sufficiency. Suppose . Then as well. Starting from , the recurrence gives an invertible remainder map modulo . The pure-cycle proof shows that it returns to remainder 0 within steps. Hence a least positive return index exists with , and is divisible by . This includes , when every remainder is 0 and .
From the return to 0, the same rule gives for all . Write with . Then , and by minimality of this is zero exactly when . Therefore divides exactly when divides .
For block 12 and , the reduced modulus is , which shares a factor 2 with 10. No positive block count works. For block 24 and , . Since , we have , so the least block count is 3. Indeed . 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.
- Encoding: I define the number, its digit or block count, its starting index and its correct append multiplier.
- State rule: I show why the old remainder determines the next remainder under this fixed rule.
- 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.
- Divisibility: every cancelled factor is coprime to the unchanged modulus, or I explicitly adjust the modulus using integer divisibility.
- 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
- If the append multiplier was wrong, revisit place value, then redo Examples 1 and 3.
- If you cancelled a factor incorrectly, return to safe division and the gcd lesson.
- If you found a pattern but could not justify it, explain the finite-state argument and reattempt Problem 4.
- If an existence proof was difficult, study pigeonhole arguments, then reattempt Problems 7 and 9 without their solutions.
- For a different recurrence application, visit first-order linear recurrences. Return to Taiwan’s study route or your optional local revision list.
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.