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"

(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{Solution}}
+
We have <math>1978^m\equiv 1978^n\pmod {1000}</math>, or <math>978^m-978^n=1000k</math> for some positive integer <math>k</math> (if it is not positive just do <math>978^n-978^m=-1000k</math>). Hence <math>978^n\mid 1000k</math>. So dividing through by <math>978^n</math> we get <math>978^{m-n}-1=\frac{1000k}{978^n}</math>. Observe that <math>2\nmid LHS</math>, so <math>2\nmid RHS</math>. So since <math>2|| 978^n</math>, clearly the minimum possible value of <math>n</math> is <math>3</math> (and then <math>489^n\mid k</math>). We will show later that if <math>n</math> is minimal then <math>m</math> is minimal. We have <math>978^{m-3}-1\equiv 0\pmod {125}\Leftrightarrow 103^{m-3}\equiv 1\pmod {125}</math>. Hence, <math>m-3\mid \varphi(125)\Rightarrow m-3\mid 100</math>. Checking by hand we find that only <math>m-3=100</math> works (this also shows that minimality of <math>m</math> depends on <math>n</math>, as claimed above). So <math>m=103</math>. Consequently, <math>m+n=106</math> with <math>\boxed{(m,n)=(103,3)}</math>.
  
−
Solution is available here:
+
The above solution was posted and copyrighted by cobbler and Andreas. The original thread for this problem can be found here: [https://aops.com/community/p393524] and [https://aops.com/community/p3332509]
 +
 
 +
==Video Solution==
 
https://www.youtube.com/watch?v=SRl4Wnd60os
 
https://www.youtube.com/watch?v=SRl4Wnd60os
 +
 +
== See Also == {{IMO box|year=1978|before=First question|num-a=2}}

Revision as of 15:57, 29 January 2021

Problem

$m$ and $n$ are positive integers with $m < n$. The last three decimal digits of $1978^m$ are the same as the last three decimal digits of $1978^n$. Find $m$ and $n$ such that $m + n$ has the least possible 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=143961"