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
  • Earth and Environmental Science
  • 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. /Ravi notices that 3⁴ = 81 ends in 1 and 3²⁰ = 3486784401 ends in 01…
AdvancedMathematicsHigh School (11–12)Pigeonhole Principle, Recursion and Graph TheoryproofNumericalOlympiad

Ravi notices that 3⁴ = 81 ends in 1 and 3²⁰ = 3486784401 ends in 01…

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.

Ravi notices that 34=813^4 = 8134=81 ends in 111 and 320=34867844013^{20} = 3486784401320=3486784401 ends in 010101. He wonders whether some power of 333 ends in the three digits 001001001.

Prove with the pigeonhole principle that there is a whole number k≥1k \ge 1k≥1 such that 3k3^k3k ends in 001001001. Look at the remainders of 31,32,…,310013^1, 3^2, \dots, 3^{1001}31,32,…,31001 on division by 100010001000. Then find the smallest such kkk with a short program.

Check your answer

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

Need a reminder? The key ideaShowHide

Remainders on division by mmm are mmm boxes. The prefix sums S0=0,S1,…,SmS_0 = 0, S_1, \dots, S_mS0​=0,S1​,…,Sm​ give a block with a sum divisible by mmm. Cut a figure into pieces: two points in one piece are close.

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.

Plan. Two powers with the same remainder give a difference divisible by 100010001000. Remove the factor 3i3^i3i.

Step 1. Pigeonholes. The 100110011001 powers 31,…,310013^1, \dots, 3^{1001}31,…,31001 have only 100010001000 possible remainders on division by 100010001000. So two of them, 3i3^i3i and 3j3^j3j with i<ji < ji<j, leave the same remainder.

Step 2. The difference. 3j−3i=3i(3j−i−1)3^j - 3^i = 3^i(3^{j - i} - 1)3j−3i=3i(3j−i−1) is divisible by 1000=23×531000 = 2^3 \times 5^31000=23×53.

Step 3. Remove the power of 3. 3i3^i3i has no factor 222 or 555, so 100010001000 divides 3j−i−13^{j - i} - 13j−i−1. With k=j−i≥1k = j - i \ge 1k=j−i≥1, the number 3k3^k3k leaves remainder 111, so it ends in 001001001.

Step 4. The smallest kkk. The program below tries k=1,2,3,…k = 1, 2, 3, \dotsk=1,2,3,… and stops at the first 3k3^k3k that leaves remainder 111. It finds k=100k = 100k=100.

Check. Ravi's 3203^{20}320 ends in 010101 but not in 001001001, so k=20k = 20k=20 is too small, which fits.

Answer: such a kkk exists, and the smallest is 100100100. Proof complete.

Log in to save this for later
← All Problems
← A set of whole numbers is chosen from 1 to 100…Ten different two-digit numbers are written on cards, for example 13, 27, 31, 44, 52, 68, 70, 85… →
More onPigeonhole Principle, Recursion and Graph Theory

Discussion (0)

Log in to join the discussion.

Loading…

Learn it in

  1. Pigeonholes in numbers and geometryThe Pigeonhole Principle

More on this topic

  1. The 15 edges of K₆ are coloured red or blue…Advanced
  2. Three houses each need a path to each of three wells, nine paths in all, drawn on flat ground…Advanced
  3. A connected planar graph with 10 vertices is drawn without crossings, and every face of the…Hard
  4. The complete bipartite graph K_(m,n) joins each of m left vertices to each of n right vertices…
Advanced
  • A river town has five land areas, A, B, C, D and E, joined by ten bridges…Hard
  • All problems on this topic →