Difference between revisions of "2001 IMO Shortlist Problems/N4"
(New page: == Problem == Let <math>p \geq 5</math> be a prime number. Prove that there exists an integer <math>a</math> with <math>1 \leq a \leq p - 2</math> such that neither <math>a^{p - 1} - 1</ma...) |
Captainsnake (talk | contribs) (→Solution (Elementary Group Theory)) |
||
(One intermediate revision by the same user not shown) | |||
Line 2: | Line 2: | ||
Let <math>p \geq 5</math> be a prime number. Prove that there exists an integer <math>a</math> with <math>1 \leq a \leq p - 2</math> such that neither <math>a^{p - 1} - 1</math> nor <math>(a + 1)^{p - 1} - 1</math> is divisible by <math>p^2</math>. | Let <math>p \geq 5</math> be a prime number. Prove that there exists an integer <math>a</math> with <math>1 \leq a \leq p - 2</math> such that neither <math>a^{p - 1} - 1</math> nor <math>(a + 1)^{p - 1} - 1</math> is divisible by <math>p^2</math>. | ||
− | == Solution == | + | == Solution (Elementary Group Theory) == |
− | {{ | + | Let us work in the group <math>(\mathbb{Z}/p^2\mathbb{Z})^{\times}</math>. |
+ | |||
+ | Note that the order of this group is <math>\phi({p^2})=p^2-p</math>. Since <math>(\mathbb{Z}/p^2\mathbb{Z})^{\times}</math> is cyclic, we know that it is isomorphic to <math>(\mathbb{Z}/(p^2-p)\mathbb{Z})^{+}</math>. | ||
+ | |||
+ | We can then conclude how many residues <math>n</math> there are such that <math>(p-1)n\equiv0\text{ (mod }p^2-p\text{)}</math>. For some arbitrary natural number <math>k</math>, one has: | ||
+ | <cmath>(p-1)n=k(p^2-p)</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> 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. | ||
+ | <cmath>\frac{p-\sqrt(p-2)-1}{2}\leq\frac{p-3}{2}</cmath> | ||
+ | <cmath>2\leq(\sqrt(p-2))</cmath> | ||
+ | <cmath>p\geq6</cmath> | ||
+ | |||
+ | 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>3^{4}\equiv6\text{ (mod }25\text{)}</cmath> | ||
== Resources == | == Resources == |
Latest revision as of 21: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
.