This is the booklet containing the problems used for training and selection purposes.
Compilation of IMO NT Problems
Compilation of APMO NT Problems
Here is a compilation of all number theory problems from APMO 1989 to 2015.
Floor and Ceiling
Floor function of where
is a real number, denoted by
is the largest integer less than or equal to
. For example,
,
and
. Is it true that, for integer
, we have
? Do you think
is correct? You can proceed if your answers to both questions are yes. It is obvious that
, and we say that
is the fractional part of
. For example,
. Clearly,
.
Problem 1: Prove that for real and integer
, we have
.
Problem 2: Prove that for real , we have
.
Solution 3: We can prove this easily this way. Write and
.
because is an integer. See the second exercise in the link above. This inequality can be treated as the triangle inequality of floor function.
Now, we will discuss Ceiling function. Ceiling of a real number ,
is the smallest integer greater than or equal to
. So,
and
as well. But
whereas
. It is clear that if
is an integer, then
. Which one is true?
The answer should be quite obvious! More precisely, if is not an integer then
. Make sense of the following identities:
You should do the following exercises to make sure you understand these functions well.
Problem 4: Is it true that for an integer
? If so, why?
Problem 5: Is it true that for an integer
? If so, why?
Problem 6: Prove that, if is an integer,
, otherwise
.
Problem 7: If is an integer,
, otherwise
.
Problem 8: If is an integer,
, otherwise
.
Latex Tutorial
Here is a tutorial on how to create documents using latex. It just covers the basics.
Euler Equation
Euler’s identity is regarded as the most beautiful equation in mathematics, since it combines five very important numbers . The identity is:
The identity is a special case of the following general one:
It has many proofs. Here is an elegant one. Let . Then
Now let’s integrate both sides. As we know and
, we have
for some constant (since it is indefinite integration). We get
We need to find the value of , so let’s set
, and we get
So and we have
Set and we have
DONE!
Chicken McNugget Theorem-The Theorem With The Weirdest Name
Here is a tutorial on chicken mcnugget theorem.
nugget
Using Matrix in Olympiad Problems
Here is a tutorial on how to use elementary matrix operations in olympiad problems. It’s version . If changes are made, it will updated later.
Thue’s Lemma – A Nice Lemma In Congruence
Thue’s Lemma is a wonderful theorem in congruence. It should have been quite popular, but unfortunately it not only isn’t very popular, it doesn’t have many resources from olympiad perspective when searched in the internet, hence the article. In this article, we prove this lemma and show some nice applications. Thanks to the user a lot randomusername of AoPS for suggesting the problems.
1. Main Lemma
Theorem 1 (Thue’s Lemma): Let be an integer and
be an integer co-prime to
. Then there are integers
with
so that
Such a solution is called a small solution sometimes.
Proof: Let i.e.
is the unique integer for which
. The number of pairs
so that
is
which is greater than
. Then there must be two different pairs
and
so that
Let and
, and we get
. Now, we need to show that
. Certainly, if one of
is zero, the other is zero as well. If both
and
are zero, that would mean that two pairs
and
are actually same. That is not the case, and so both
can not be
. Therefore, none of
or
is
, and we are done.
Corollary 2: For a prime and an integer
, there are integers
with
such that
This lemma can be generalized even more with the same proof.
Theorem 3 (Generalization of Thue’s Lemma): Let and
are two real numbers so that
. Then for an integer
, there are integers
with
and
so that,
And we can even make this lemma a two dimensional one.
Theorem 4 (Two Dimensional Thue’s Lemma): Let and
be arbitrary integers. There exist
with at least one of
non-zero such that
2. Applications
First we show an elegant proof of Fermat’s theorem here using a well known theorem and Thue’s theorem (1).
Definition 5 (Bisquare): The sum of two perfect squares which are co-prime to each other is a bisquare.
Definition 6 (Quadratic Residue): is a quadratic residue of a prime
if there exist an integer
so that,
is a quadratic non-residue if there doesn’t exist any such integer
that,
Definition 7: Two integers and
are co-prime if their greatest common divisor
. We denote this by
.
To prove Fermat’s theorem, we will use the following theorem without proof, which is pretty well known and posted so many times on AoPS.
Theorem 8: is a quadratic residue of a prime
if and only if
is of the form
.
Theorem 9 (Fermat’s Theorem): Every prime of the form
can be written as a bisquare.
Proof: We already know that, for , there is an
so that,
From Thue’s theorem, for such an , there are integers
with
so that,
The last congruence means that , so
Therefore, must occur.
In fact, we can use the same technique for generalizing Fermat’s theorem.
Theorem 10: Let . If
is a quadratic residue of a prime
, then there are integers
so that,
.
Proof: We have already proven the case . If
is a quadratic residue of
,
has a solution. Fix the integer , and take
as in Thue’s lemma so that,
We make two cases for .
-
. Then
. So, either
or
. If it’s the first, we are done. If not, we see that
must be even. Assume
and we get
, as desired.
- Now,
, so
. If
, then
and
are both odd or both even. If both are even, then
is divisible by
, a contradiction since
is odd. Otherwise,
and
are both odd.
Again, contradiction. We are left with the case
. This shows
is divisible by
. If we take
, we get
.
Corollary 11: For a prime and an integer
, there exists integers
so that
divides
if and only if
is a quadratic residue of
.
Proof: Without loss of generality, we can take and
to be co-prime and
not divisible by
. First assume,
, then
must be co-prime to
. Therefore,
has an inverse modulo
, assume
.
For the only if portion, we have is a quadratic residue of
, let
. Clearly,
otherwise
will divide
. From Thue’s lemma, there are integers
with
We can use these results to imply the following theorem also.
Theorem 12: For , if
for some
, then every divisor
of
is of the same form.
Proof: Remember the identity:
This means that the product of two numbers of the form is of the same form. From theorems above, if
is a divisor of
, then
for some
. The identity clearly says that, if
, then any power of
,
is of this form again. Let’s assume that, the prime factorization of
is,
From the lemma, for any ,
is of this form. So,
is of the same form as well. So, for any divisor
is of the same form again. Repeating this upto
we get that,
is of the same form again.
Now we prove another theorem that demonstrates the power of Thue’s theorem. We will use the following theorem without proof.
Theorem 13: is a quadratic residue of
if and only if
is of the form
.
Theorem 14: If is a prime of the form
, there are integers
such that
.
Proof: Since is of the form
,
is a quadratic residue of
. Take
to be an odd integer for which
or,
Such an exists, since
is odd. Even if
is even,
has a solution. For that
, we get,
because is odd. From Thue’s theorem, there are integers
with
such that,
Then we also get
Because ,
. On the other hand,
Either or
. We can easily check that
can not happen (try yourself).
3. Problems
Assume that you know Thue’s lemma. How do we get that we need this particular lemma here? And how do we approach? If you saw the previous proof of the sum of squares theorems, you should understand the main advantage of using Thue’s lemma. The idea of small solutions is crucial here. For that, we can bound some integers here. First try to prove the following two theorems in a similar fashion to the previous theorems.
Theorem 15: Let be a prime so that,
divides
for some integer
. Show that, there are integers
such that,
.
Theorem 16: If is a prime of the form
, there is at least one prime
in the interval
which is a quadratic non-residue of
.
Proving these two theorems should be fairly easy. Now we see some applications.
Problem 17: Let be a prime for which there exists a positive integer
such that
divides
. Prove that, there exist integers
and
so that,
.
Solution 18: We have . Since we want to bound
, it is obvious, we should find
so that
divides
and then bound it. This is where Thue’s lemma comes in. Fix the integer
, which is clearly co-prime to
. Then from Thue’s lemma, we there are integers
with
so that,
This gives us what we need. Note that,
Thus, divides
, and now we get to use the fact:
We immediately get that .
Problem 19: Let be an integer. Prove that if the equation
has a rational solution, then it also has an integer solution.
Problem 20 (Iran Olympiad, rd Round): Let
be a prime number. Prove that, there exists integers
such that
if and only if
.
Problem 21 (Polish Math Olympiad Problem): Let be a set of all positive integers which can be represented as
for some integers
such that
. Let
be a prime number such that
for some integer
. Show that if for some positive integer
the number
is in
, then
is in
as well.
Problem 22: Prove that the equation has no solution in integers.
বিভাজ্যতা(প্রথম অংশ, বিগিনারদের জন্য)
সংজ্ঞাঃ এর মানে হচ্ছে
দিয়ে
বিভাজ্য, অর্থাৎ
কে
দিয়ে ভাগ করলে ভাগশেষ ০ হয়। এখানে
কে বলে ভাজক(divisor) বা উৎপাদক(factor), এবং
কে বলে
এর গুণিতক(multiple)।
যেমন দিয়ে বিভাজ্য। নোটেশন ব্যবহার করে
.
এখন এর কিছু বৈশিষ্ট্য দেখা যাক।
হলে অবশ্যই
- যদি
হয় যাতে করে
এর মান
এর চেয়ে কম, তাহলে
হতে হবে।
হলে
একটি পূর্ণসংখ্যা হবে যা আসলে এদের ভাগফল। ধরি ভাগফল হচ্ছে
. তার মানে এমন পূর্ণসংখ্যা
থাকবে যাতে
. তার মানে প্রত্যেকটা বিভাজ্যতা আসলে একটা সমীকরণ বলা যায়। শুধু আমরা সুবিধার জন্য এভাবে ব্যবহার করি। নয়তো সরাসরি ও করা যাবে, কিন্তু শুধু শুধু কষ্ট করা লাগবে।
.
হলে যে কোন পূর্ণসংখ্যা
এর জন্য
. কারণ,
লেখা যায়। তখন
যা
দিয়ে বিভাজ্য। এটা খুবই গুরুত্বপূর্ণ একটা বৈশিষ্ট্য। সমস্যা সমাধান করতে গেলে দেখা যাবে।
আপাতত সমস্যায় চলে যাই।
১। এমন সব ধনাত্মক পূর্ণসংখ্যা বের কর যাতে করে
.
সমাধানঃ বিভাজ্যতার ডানে আছে যা আমরা জানি না। তাই আমাদের পরম দায়িত্ব হচ্ছে একে সরানো। একে সরানোর জন্যই উপরের সাহায্য লাগবে। কিভাবে?
দেখো, ডানে এর সহগ হচ্ছে
. এখন আমরা তো চাইলেই
এর যে কোন গুণিতক বাদ দিতে পারি। এজন্য আমাদের লাগবে
. এখন
কে চাইলেই বাদ দেওয়া যায়। কারণ
. তার মানে
এর প্রত্যেকটি ভাজকের জন্য এক-একটি করে সমাধান পাওয়া যাবে। অর্থাৎ
২। এই সমীকরণের কয়টি সমাধান থাকবে?
সমাধানঃ খেয়াল করে দেখো যে এখানে এর কোন ভাজক হলে, প্রত্যেকটি ভাজকের জন্যই একটি করে
মানে একটি করে সমাধান পাওয়া যাবে। তার মানে সমাধান সংখ্যা হবে
এর ভাজকসংখ্যা। এখন, ১২ এর ভাজক হচ্ছে ১,২,৩,৪,৬,১২ এই ছয়টি। তাই এই সমীকরণের সমাধানের সংখ্যা ও ছয়টি। আমরা সমীকরণকে এইভাবে ও লিখতে পারি
.
এখন থেকে আমরা কোন সংখ্যা এর ভাজক সংখ্যা(number of divisor) প্রকাশ করবো
দিয়ে। মানে উপরের উদাহরণে
. এই সমস্যা থেকে আরো একটা দরকারী কিছু শিখা যায়। যদি কোন সমীকরণের সমাধান সংখ্যা বের করতে বলা হয়, তাহলে সবার আগে ঐটাকে কোনভাবে একটা এই ধরনের সমীকরণের সমাধানের সংখ্যা যদি বের করতে বলা হয় তাহলে সবার আগে চিন্তা করা দরকার তাকে কোনভাবে এই ধরনের বিভাজ্যতা বানানো যায় কিনা। তাহলেই সেটা কোন কিছুর ভাজকসংখ্যা হবে।
সমস্যাঃ এমন সব ধনাত্মক পূর্ণসংখ্যা বের কর যাতে
.
সমাধানঃ এবার দেখো ডানে এর সহগ
আর বামে
. তাই বামে ৩ দিয়ে গুন করে আগে ৬ বানিয়ে নিতে হবে।
. আবার বিয়োগ,
. তাহলে
. কিন্তু যেহেতু
তাই
. সেজন্য
.
আচ্ছা, একটা ব্যাপার কি পরিষ্কার? আমরা আসলে কি করতে চাই? এর মান যেহেতু জানি না, তাই ডান পাশ থেকে যদি কোন ভাবে
কে সরানো যায়, তাহলে আমরা একটা সাংখ্যিক মান পেয়ে যাই। তখন আমরা সমাধান করতে পারবো। তাই দুইপাশে
এর সহগ সমান করা দরকার। তার মানে একপাশে যদি সহগ থাকে
আর অন্য পাশে থাকে
তাহলে আমাদের আনতে হবে
আর
এর লসাগু, অথবা তাদের গুণফল যাতে পরে তাদের কাটা যায়।