Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Shortlist Problems/N4"

(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.)
(→‎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>, 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>, more specifically, it implies that if and only if <math>a_0</math> has this property, so does <math>\frac{1}{a_0}</math> and <math>\frac{1}{a^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 propert.
+
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 21:27, 16 October 2020

Problem

Let $p \geq 5$ be a prime number. Prove that there exists an integer $a$ with $1 \leq a \leq p - 2$ such that neither $a^{p - 1} - 1$ nor $(a + 1)^{p - 1} - 1$ is divisible by $p^2$.

Solution (Elementary Group Theory)

Let us work in the group $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$.

Note that the order of this group is $\phi({p^2})=p^2-p$. Since $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$ is cyclic, we know that it is isomorphic to $(\mathbb{Z}/(p^2-p)\mathbb{Z})^{+}$.

We can then conclude how many residues $n$ there are such that $(p-1)n\equiv0\text{ (mod }p^2-p\text{)}$. For some arbitrary natural number $k$, one has: \[(p-1)n=k(p^2-p)\] \[n=kp\] Therefore there are only $p$ possible values of $n$. It's also notable that if this is true for $n_0$, then it is also true for $p^2-p-n_0$ and $2n_0$. This implies that there are also $p$ different values of a such that $a^{p-1}\equiv 1\text{ (mod }p^2\text{)}$. It also implies that if and only if $a_0$ has this property, so does $\frac{1}{a_0}$, $a_0^2$ and $\frac{1}{a_0^2}$ when working in $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$. The squares also have their inverses which are guaranteed to have the property.

There exists no numbers $1<m_1,m_2\leq p-2$ such that $m_1m_2\equiv1\text{ (mod }p^2\text{)}$ as $(p-2)(p-2)<p^2$ and $2^2>1$. Therefore, at most half of the values where $a_0^{p-1}\equiv 1\text{ (mod }p^2\text{)}$ are in range $1<a_0\leq p-2$. We can again remove some of the potential values by squaring all $a_0\geq\sqrt{p}$ 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 $a$ and $a+1$ that satisfy the requirements by the pigeonhole principle. \[\frac{p-\sqrt(p-2)-1}{2}\leq\frac{p-3}{2}\] \[2\leq(\sqrt(p-2))\] \[p\geq6\]

Lastly, you must show that there is a pair for $p=5$. This is satisfied by $a=2$. \[2^{4}\equiv16\text{ (mod }25\text{)}\] \[3^{4}\equiv6\text{ (mod }25\text{)}\]

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/N4&oldid=135154"