Difference between revisions of "2001 IMO Shortlist Problems/N4"
Captainsnake (talk | contribs) (Added solution. My solution uses group theory, I suspect there is a very similar line of reasoning that can be written in the language of modular arithmetic, but I couldn't think of one.) |
Captainsnake (talk | contribs) (→Solution (Elementary Group Theory)) |
||
Line 10: | Line 10: | ||
<cmath>(p-1)n=k(p^2-p)</cmath> | <cmath>(p-1)n=k(p^2-p)</cmath> | ||
<cmath>n=kp</cmath> | <cmath>n=kp</cmath> | ||
− | Therefore there are only <math>p</math> possible values of <math>n</math>. It's also notable that if this is true for <math>n_0</math>, then it is also true for <math>p^2-p-n_0</math> | + | Therefore there are only <math>p</math> possible values of <math>n</math>. It's also notable that if this is true for <math>n_0</math>, then it is also true for <math>p^2-p-n_0</math> and <math>2n_0</math>. This implies that there are also <math>p</math> different values of a such that <math>a^{p-1}\equiv 1\text{ (mod }p^2\text{)}</math>. It also implies that if and only if <math>a_0</math> has this property, so does <math>\frac{1}{a_0}</math>, <math>a_0^2</math> and <math>\frac{1}{a_0^2}</math> when working in <math>(\mathbb{Z}/p^2\mathbb{Z})^{\times}</math>. The squares also have their inverses which are guaranteed to have the property. |
There exists no numbers <math>1<m_1,m_2\leq p-2</math> such that <math>m_1m_2\equiv1\text{ (mod }p^2\text{)}</math> as <math>(p-2)(p-2)<p^2</math> and <math>2^2>1</math>. Therefore, at most half of the values where <math>a_0^{p-1}\equiv 1\text{ (mod }p^2\text{)}</math> are in range <math>1<a_0\leq p-2</math>. We can again remove some of the potential values by squaring all <math>a_0\geq\sqrt{p}</math> and taking their inverse. As long as no more than half of the values in that range can have the required property, there must be a pair <math>a</math> and <math>a+1</math> that satisfy the requirements by the pigeonhole principle. | There exists no numbers <math>1<m_1,m_2\leq p-2</math> such that <math>m_1m_2\equiv1\text{ (mod }p^2\text{)}</math> as <math>(p-2)(p-2)<p^2</math> and <math>2^2>1</math>. Therefore, at most half of the values where <math>a_0^{p-1}\equiv 1\text{ (mod }p^2\text{)}</math> are in range <math>1<a_0\leq p-2</math>. We can again remove some of the potential values by squaring all <math>a_0\geq\sqrt{p}</math> and taking their inverse. As long as no more than half of the values in that range can have the required property, there must be a pair <math>a</math> and <math>a+1</math> that satisfy the requirements by the pigeonhole principle. | ||
Line 17: | Line 17: | ||
<cmath>p\geq6</cmath> | <cmath>p\geq6</cmath> | ||
− | Lastly, you must show that there is a pair for <math>p=5</math>. | + | Lastly, you must show that there is a pair for <math>p=5</math>. This is satisfied by <math>a=2</math>. |
<cmath>2^{4}\equiv16\text{ (mod }25\text{)}</cmath> | <cmath>2^{4}\equiv16\text{ (mod }25\text{)}</cmath> | ||
<cmath>3^{4}\equiv6\text{ (mod }25\text{)}</cmath> | <cmath>3^{4}\equiv6\text{ (mod }25\text{)}</cmath> | ||
+ | |||
== Resources == | == Resources == | ||
Latest revision as of 22:27, 16 October 2020
Problem
Let be a prime number. Prove that there exists an integer
with
such that neither
nor
is divisible by
.
Solution (Elementary Group Theory)
Let us work in the group .
Note that the order of this group is . Since
is cyclic, we know that it is isomorphic to
.
We can then conclude how many residues there are such that
. For some arbitrary natural number
, one has:
Therefore there are only
possible values of
. It's also notable that if this is true for
, then it is also true for
and
. This implies that there are also
different values of a such that
. It also implies that if and only if
has this property, so does
,
and
when working in
. The squares also have their inverses which are guaranteed to have the property.
There exists no numbers such that
as
and
. Therefore, at most half of the values where
are in range
. We can again remove some of the potential values by squaring all
and taking their inverse. As long as no more than half of the values in that range can have the required property, there must be a pair
and
that satisfy the requirements by the pigeonhole principle.
Lastly, you must show that there is a pair for . This is satisfied by
.