Skip to main content
OlympiadHQ

Browse · MathNet

Print

India_2017

India 2017 number theory

Problem

Let and be two integers and define , and for . If is a prime such that is divisible by , then show that there are integers and such that does not divide for any .
Solution
Let be an integer such that divides . There exists such an integer since is divisible by . Let and . Then Therefore, if and then . By induction, it is easy to see that . Since , it follows that does not divide . Therefore does not divide for any .

Techniques

Quadratic residuesRecurrence relations