HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Problems
  2. /A ring has 89 cells, numbered 0 to 88 clockwise…
AdvancedMathematicsHigh School (11–12)Number TheoryNumericalOlympiad

A ring has 89 cells, numbered 0 to 88 clockwise…

StemPy LabContributed by StemPy Lab

Try it on paper first. A hint, the key idea and the worked solution are here when you need them.

A ring has 898989 cells, numbered 000 to 888888 clockwise. A robot starts at cell 000 and each move takes it 343434 cells clockwise. Find the least number of moves after which the robot is on cell 111. Use the extended Euclidean algorithm on 898989 and 343434; the remainders you meet are Fibonacci numbers. Then find the least number of moves after which it is on cell 888888, one cell anticlockwise of the start.

Check your answer

Work it out on paper, then type your number. The answer itself stays hidden.

Need a reminder? The key ideaShowHide

ax≡b(modm)ax \equiv b \pmod max≡b(modm) is solvable exactly when d=gcd⁡(a,m)d = \gcd(a, m)d=gcd(a,m) divides bbb, and then it has ddd solutions modulo mmm:

ax≡b(modm)  ⟺  adx≡bd(modmd).\displaystyle ax \equiv b \pmod m \iff \tfrac{a}{d}x \equiv \tfrac{b}{d} \pmod{\tfrac{m}{d}}.ax≡b(modm)⟺da​x≡db​(moddm​).

The worked solution

Check an answer or open a hint to unlock the worked solution.

Have you tried it?

Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.

Given. Cell after xxx moves: 34x mod 8934x \bmod 8934xmod89.

Plan. Solve 34x≡1(mod89)34x \equiv 1 \pmod{89}34x≡1(mod89) with the extended Euclidean algorithm, then use 88≡−188 \equiv -188≡−1.

Step 1. Divide. 89=2×34+2189 = 2 \times 34 + 2189=2×34+21, 34=21+1334 = 21 + 1334=21+13, 21=13+821 = 13 + 821=13+8, 13=8+513 = 8 + 513=8+5, 8=5+38 = 5 + 38=5+3, 5=3+25 = 3 + 25=3+2, 3=2+13 = 2 + 13=2+1.

Step 2. Work back. Start from 1=3−21 = 3 - 21=3−2 and replace each remainder by the line that made it. The numbers climb the Fibonacci list:

1=2×3−5=2×8−3×5=5×8−3×13=5×21−8×13=13×21−8×34=13×89−34×341 = 2 \times 3 - 5 = 2 \times 8 - 3 \times 5 = 5 \times 8 - 3 \times 13 = 5 \times 21 - 8 \times 13 = 13 \times 21 - 8 \times 34 = 13 \times 89 - 34 \times 341=2×3−5=2×8−3×5=5×8−3×13=5×21−8×13=13×21−8×34=13×89−34×34.

Step 3. Multiply out. 13×89=115713 \times 89 = 115713×89=1157 and 34×34=115634 \times 34 = 115634×34=1156. The difference is 111, so the identity is right.

Step 4. Read off. Modulo 898989 the term 13×8913 \times 8913×89 is 000, so −34×34≡1-34 \times 34 \equiv 1−34×34≡1. The inverse of 343434 is −34≡55-34 \equiv 55−34≡55.

Step 5. Cell 88. The same identity says 34×34≡−1≡88(mod89)34 \times 34 \equiv -1 \equiv 88 \pmod{89}34×34≡−1≡88(mod89). So 343434 moves bring the robot to cell 888888.

Check. 34×55=1870=21×89+134 \times 55 = 1870 = 21 \times 89 + 134×55=1870=21×89+1 leaves 111, and 34×34=1156=12×89+8834 \times 34 = 1156 = 12 \times 89 + 8834×34=1156=12×89+88 leaves 888888. Also 55+34=8955 + 34 = 8955+34=89, as it must be: the two answers are negatives of each other modulo 898989.

Answer: 555555 moves to reach cell 111, and 343434 moves to reach cell 888888.

Watch out. The most common slip in the back substitution is a lost sign. Always multiply out the identity, as in Step 3. Here a negative coefficient, −34-34−34, is turned into the positive inverse 555555.

Log in to save this for later
← All Problems
← A machine prints a code x from 0 to 37 that must satisfy 14x ≡ 22 pmod38…Prove the cancellation rule: if ac ≡ bc pmod m and d = gcd(c, m), then a ≡ b pmodm/d… →
More onNumber Theory

Discussion (0)

Log in to join the discussion.

Loading…

More on this topic

  1. The triangular numbers are 1, 3, 6, 10, …, where the nth one is (n(n + 1))/2…Advanced
  2. Prove that the equation x³ + y³ + z³ = n has no solution in integers when n leaves remainder 4 or 5…Advanced
  3. Find every triple of positive integers a ≤ b ≤ c with 1/a + 1/b + 1/c = 1, and prove that there are…Advanced
  4. Find all pairs of positive integers (x, y) with x² - y² = 945…Hard
  5. A teacher wants a list of every primitive Pythagorean triple whose hypotenuse is less than 100…Advanced
All problems on this topic →