Difference between revisions of "1990 IMO Problems/Problem 3"
m (→Solution 3) |
m (→Solution 3) |
||
Line 27: | Line 27: | ||
Now if <math>r\neq 2\mid n</math> then we can't have <math>r\mid p-1</math> because then <math>r\le p-1</math> contradiction. Therefore <math>r=2</math> and since <math>n</math> is odd <math>\gcd(2n, p-1)=2</math>. Hence<cmath>p\mid 2^2-1 \implies p=3</cmath>Let <math>v_3(n)=k</math>. By lifting the exponent we must have<cmath>v_3(2^n+1)=1+k\ge v_3(n^2)=2k \implies k=1</cmath>Let <math>n=3n_1</math>. <math>n_1=1</math> is a solution (<math>2^3+1=3^2=9</math>). Assume <math>n_1\neq 1</math> and let <math>\pi(n_1)=q\neq 3</math>. By Chinese Remainder Theorem since <math>q\neq 3</math> we have: | Now if <math>r\neq 2\mid n</math> then we can't have <math>r\mid p-1</math> because then <math>r\le p-1</math> contradiction. Therefore <math>r=2</math> and since <math>n</math> is odd <math>\gcd(2n, p-1)=2</math>. Hence<cmath>p\mid 2^2-1 \implies p=3</cmath>Let <math>v_3(n)=k</math>. By lifting the exponent we must have<cmath>v_3(2^n+1)=1+k\ge v_3(n^2)=2k \implies k=1</cmath>Let <math>n=3n_1</math>. <math>n_1=1</math> is a solution (<math>2^3+1=3^2=9</math>). Assume <math>n_1\neq 1</math> and let <math>\pi(n_1)=q\neq 3</math>. By Chinese Remainder Theorem since <math>q\neq 3</math> we have: | ||
− | \begin{eqnarray*} q\mid 8^{n_1}+1\mid 8^{2n_1}-1 \text{ and } q\mid 8^{q-1}-1 \\ \implies q\mid 8^{\gcd(2n_1, q-1)}-1=63 \text{ so } q=7 \end{eqnarray*} | + | <cmath>\begin{eqnarray*} |
+ | q\mid 8^{n_1}+1\mid 8^{2n_1}-1 \text{ and } q\mid 8^{q-1}-1 | ||
+ | \\ \implies q\mid 8^{\gcd(2n_1, q-1)}-1=63 \text{ so } q=7 | ||
+ | \end{eqnarray*}</cmath> | ||
However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction. | However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction. |
Revision as of 18:15, 7 August 2021
Problem
Determine all integers such that
is an integer.
Solution 1
Let be the set of all solutions and
be the set of all prime factors of the solutions.
It is clear that the smallest element of is 3.
Assume that
and let's try to determine the second smallest element
.
Let be a multiple of
. It is important to notice that
(otherwise it is easy to get that any power of
divides
, a non-sense). Therefore,
where
or
and
does not have prime divisors smaller than
.
Since
, the multiplicative order
of 2 modulo
divides
. Moreover,
must be even, since otherwise we would have
, a contradiction to the required
.
Since
we must have
or
. But the numbers
and
deliver only one new prime factor
, implying that
. However, in this case
, a contradiction. This contradiction proves that
and thus
.
This solution was posted and copyrighted by maxal/orl. The original thread for this problem can be found here: [1]
Solution 2
Let be the smallest prime divisor of
. It is easy to check that,
is obviously solution. Let
.
and
(By the fermat's theorem), we obtain that
. It is also obvious that n is an odd number.
Lemma: For all
positive integers,
is a primitive root modulo
.
. Using the lemma, we get that
. Using the power of three, we obtain that
. This is only possible when
. So
. Now
be the second smallest prime divisor of
.
. If this equals to 2, we get
which is a contradiction.If
then
. We know that
is different from
. Hence
must be
. But this is impossible since
when
is divisible by
. Hence the answer is
.
This solution was posted and copyrighted by grumpyorum. The original thread for this problem can be found here: [2]
Solution 3
Trivially is a solution. Now assume
and define
to be the smallest prime divisor of
. Let
. Then we have:
Now if then we can't have
because then
contradiction. Therefore
and since
is odd
. Hence
Let
. By lifting the exponent we must have
Let
.
is a solution (
). Assume
and let
. By Chinese Remainder Theorem since
we have:
However contradiction.
The solutions are henceforth .
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [3]
Solution 4
et and
be the smallest prime factor of
.Then
.
Thus
for some positive
and
.
Also
.
Thus for some positive integer
.
Now let
and
be the smallest prime divisor of
.Then we can deduce that
(Note that
is
or
).
But this gives which is false as
leaves remainders
modulo
.
Thus and
if
.
Thus the solutions are and
This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [4]
Many more solutions can be found in the thread in Contest Collections.
See Also
1990 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |