Difference between revisions of "1984 IMO Problems/Problem 2"
(Created page with "==Problem== Find one pair of positive integers <math>a,b</math> such that <math>ab(a+b)</math> is not divisible by <math>7</math>, but <math>(a+b)^7-a^7-b^7</math> is divisibl...") |
(→Solution 2) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
Find one pair of positive integers <math>a,b</math> such that <math>ab(a+b)</math> is not divisible by <math>7</math>, but <math>(a+b)^7-a^7-b^7</math> is divisible by <math>7^7</math>. | Find one pair of positive integers <math>a,b</math> such that <math>ab(a+b)</math> is not divisible by <math>7</math>, but <math>(a+b)^7-a^7-b^7</math> is divisible by <math>7^7</math>. | ||
− | ==Solution== | + | == Solution 1 == |
So we want <math>7 \nmid ab(a+b)</math> and <math>7^7 | (a+b)^7-a^7-b^7 = 7ab(a+b)(a^2+ab+b^2)^2</math>, so we want <math>7^3 | a^2+ab+b^2</math>. | So we want <math>7 \nmid ab(a+b)</math> and <math>7^7 | (a+b)^7-a^7-b^7 = 7ab(a+b)(a^2+ab+b^2)^2</math>, so we want <math>7^3 | a^2+ab+b^2</math>. | ||
Now take e.g. <math>a=2,b=1</math> and get <math>7|a^2+ab+b^2</math>. Now by some standard methods like Hensels Lemma (used to the polynomial <math>x^2+x+1</math>, so <math>b</math> seen as constant from now) we get also some <math>\overline{a}</math> with <math>7^3 | \overline{a}^2+\overline{a}b+b^2</math> and <math>\overline{a} \equiv a \equiv 2 \mod 7</math>, so <math>7\nmid \overline{a}b(\overline{a}+b)</math> and we are done. (in this case it gives <math>\overline{a}=325</math>) | Now take e.g. <math>a=2,b=1</math> and get <math>7|a^2+ab+b^2</math>. Now by some standard methods like Hensels Lemma (used to the polynomial <math>x^2+x+1</math>, so <math>b</math> seen as constant from now) we get also some <math>\overline{a}</math> with <math>7^3 | \overline{a}^2+\overline{a}b+b^2</math> and <math>\overline{a} \equiv a \equiv 2 \mod 7</math>, so <math>7\nmid \overline{a}b(\overline{a}+b)</math> and we are done. (in this case it gives <math>\overline{a}=325</math>) | ||
This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [https://aops.com/community/p366644] | This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [https://aops.com/community/p366644] | ||
+ | |||
+ | == Solution 2 == | ||
+ | Lemma: <math>a^{7} \equiv a (mod 7) </math>. | ||
+ | |||
+ | Proof: Recall that if <math>7 \nmid x </math>, then <math>x^{3} \equiv 1, -1 (mod 7) </math>. | ||
+ | |||
+ | Therefore, <math>x^{6} \equiv 1 (mod 7) </math>. | ||
+ | |||
+ | <math>\implies </math> <math>a^{7} \equiv a (mod 7) </math> <math>\forall </math> <math>a \not\equiv 0 (mod 7) </math>. | ||
+ | |||
+ | However, if <math>7|x </math>, then <math>a^{7} \equiv a (mod 7) </math>. | ||
+ | |||
+ | So now, we need to find one pair of integers (a, b) such that <math>(a+b)^{7} - a^{7} - b^{7} \equiv 0 (mod 7) </math>. This means <math>(a+b)^{7} \equiv a^{7} + b^{7} (mod 7) </math>. | ||
+ | <math>\implies (a+b) \equiv a+b (mod 7) </math>. But this is true for all pairs of integers (a, b). So any random pair of integers would work. | ||
+ | |||
+ | Footnote: Even a pair of integers (a, b) which satisfies <math>7|ab(a+b) </math> would work. So the condition given is irrelevant. Try it! | ||
== See Also == {{IMO box|year=1984|num-b=1|num-a=3}} | == See Also == {{IMO box|year=1984|num-b=1|num-a=3}} |
Latest revision as of 09:04, 25 May 2024
Contents
Problem
Find one pair of positive integers such that
is not divisible by
, but
is divisible by
.
Solution 1
So we want and
, so we want
.
Now take e.g.
and get
. Now by some standard methods like Hensels Lemma (used to the polynomial
, so
seen as constant from now) we get also some
with
and
, so
and we are done. (in this case it gives
)
This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]
Solution 2
Lemma: .
Proof: Recall that if , then
.
Therefore, .
.
However, if , then
.
So now, we need to find one pair of integers (a, b) such that . This means
.
. But this is true for all pairs of integers (a, b). So any random pair of integers would work.
Footnote: Even a pair of integers (a, b) which satisfies would work. So the condition given is irrelevant. Try it!
See Also
1984 IMO (Problems) • Resources | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |