Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1978 IMO Problems/Problem 1"
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
<math>m</math> and <math>n</math> are positive integers with <math>m < n</math>. The last three decimal digits of <math>1978^m</math> are the same as the last three decimal digits of <math>1978^n</math>. Find <math>m</math> and <math>n</math> such that <math>m + n</math> has the least possible value.
+
Let <math> m</math> and <math> n</math> be positive integers such that <math> 1 \le m < n</math>. In their decimal representations, the last three digits of <math> 1978^m</math> are equal, respectively, to the last three digits of <math> 1978^n</math>. Find <math> m</math> and <math> n</math> such that <math> m + n</math> has its least value.
  
 
==Solution==
 
==Solution==

Latest revision as of 23:21, 20 October 2021

Problem

Let $m$ and $n$ be positive integers such that $1 \le m < n$. In their decimal representations, the last three digits of $1978^m$ are equal, respectively, to the last three digits of $1978^n$. Find $m$ and $n$ such that $m + n$ has its least value.

Solution

We have $1978^m\equiv 1978^n\pmod {1000}$, or $978^m-978^n=1000k$ for some positive integer $k$ (if it is not positive just do $978^n-978^m=-1000k$). Hence $978^n\mid 1000k$. So dividing through by $978^n$ we get $978^{m-n}-1=\frac{1000k}{978^n}$. Observe that $2\nmid LHS$, so $2\nmid RHS$. So since $2|| 978^n$, clearly the minimum possible value of $n$ is $3$ (and then $489^n\mid k$). We will show later that if $n$ is minimal then $m$ is minimal. We have $978^{m-3}-1\equiv 0\pmod {125}\Leftrightarrow 103^{m-3}\equiv 1\pmod {125}$. Hence, $m-3\mid \varphi(125)\Rightarrow m-3\mid 100$. Checking by hand we find that only $m-3=100$ works (this also shows that minimality of $m$ depends on $n$, as claimed above). So $m=103$. Consequently, $m+n=106$ with $\boxed{(m,n)=(103,3)}$.

The above solution was posted and copyrighted by cobbler and Andreas. The original thread for this problem can be found here: [1] and [2]

Video Solution

https://www.youtube.com/watch?v=SRl4Wnd60os

See Also

1978 IMO (Problems) • Resources
Preceded by
First question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1978_IMO_Problems/Problem_1&oldid=163837"