Difference between revisions of "1978 IMO Problems/Problem 1"
Hashtagmath (talk | contribs) (Created page with "==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 thre...") |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | <math>m</math> and <math>n</math> | + | 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== | ||
− | {{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>. |
+ | |||
+ | 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 | ||
+ | |||
+ | == See Also == {{IMO box|year=1978|before=First question|num-a=2}} |
Latest revision as of 23:21, 20 October 2021
Contents
Problem
Let and be positive integers such that . In their decimal representations, the last three digits of are equal, respectively, to the last three digits of . Find and such that has its least value.
Solution
We have , or for some positive integer (if it is not positive just do ). Hence . So dividing through by we get . Observe that , so . So since , clearly the minimum possible value of is (and then ). We will show later that if is minimal then is minimal. We have . Hence, . Checking by hand we find that only works (this also shows that minimality of depends on , as claimed above). So . Consequently, with .
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 |