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