# 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) (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.) |
||

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>, 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. | ||

+ | |||

+ | 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>. | ||

+ | <cmath>2^{4}\equiv16\text{ (mod }25\text{)}</cmath> | ||

+ | <cmath>3^{4}\equiv6\text{ (mod }25\text{)}</cmath> | ||

== Resources == | == Resources == | ||

## Revision as of 22:23, 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 , more specifically, it 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 propert.

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 .