Floor and Ceiling

Floor function of {x} where {x} is a real number, denoted by {\lfloor x\rfloor} is the largest integer less than or equal to {x}. For example, {\lfloor 3.1415\rfloor=3}, {\lfloor-2\rfloor=-2} and {\lfloor5\rfloor=5}. Is it true that, for integer {x}, we have {\lfloor x\rfloor =x}? Do you think {\lfloor x\rfloor\leq x<\lfloor x\rfloor+1} is correct? You can proceed if your answers to both questions are yes. It is obvious that {x\geq\lfloor x\rfloor}, and we say that {\{x\}=x-\lfloor x\rfloor} is the fractional part of {x}. For example, {\{3.14\}=3.14-3=.14}. Clearly, {0\leq\{x\}<1}.
Problem 1: Prove that for real {x} and integer {n}, we have {\lfloor x+n\rfloor=\lfloor x\rfloor+n}.

Problem 2: Prove that for real {x,y}, we have {\lfloor x+y\rfloor\geq\lfloor x\rfloor+\lfloor y\rfloor}.

Solution 3: We can prove this easily this way. Write {x=\lfloor x\rfloor+\{x\}} and {y=\lfloor y\rfloor+\{y\}}.

\displaystyle \begin{array}{rcl} \lfloor x+y\rfloor & = & \lfloor \lfloor x\rfloor+\{x\}+\lfloor y\rfloor+\{y\}\rfloor\\ & = & \lfloor x\rfloor+\lfloor y\rfloor+\lfloor\{x\}+\{y\}\rfloor\\ &\geq&\lfloor x\rfloor+\lfloor y\rfloor \end{array}

because {\lfloor x\rfloor+\lfloor y\rfloor} 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 {x}, {\lceil x\rceil} is the smallest integer greater than or equal to {x}. So, {\lceil3.14\rceil=4} and {\lceil4\rceil=4} as well. But {\lceil-4.1\rceil=-4} whereas {\lceil4.1\rceil=5}. It is clear that if {x} is an integer, then {\lceil x\rceil=\lfloor x\rfloor=x}. Which one is true?

  1. {\lceil x\rceil\geq\lfloor x\rfloor}
  2. {\lceil x\rceil\leq\lfloor x\rfloor}

The answer should be quite obvious! More precisely, if {x} is not an integer then {\lceil x\rceil=1+\lfloor x\rfloor}. Make sense of the following identities:

\displaystyle \lfloor \lfloor x\rfloor\rfloor=\lfloor x\rfloor

\displaystyle \lceil \lceil x\rceil\rceil=\lceil x\rceil

\displaystyle \{\{x\}\}=\{x\}

You should do the following exercises to make sure you understand these functions well.
Problem 4: Is it true that {\lceil x+n\rceil=\lceil x\rceil+n} for an integer {n}? If so, why?

Problem 5: Is it true that {\{ x+n\}=\{ x\}} for an integer {n}? If so, why?

Problem 6: Prove that, if {x} is an integer, {\lfloor x\rfloor+\lfloor -x\rfloor=0}, otherwise {-1}.

Problem 7: If {x} is an integer, {\lceil x\rceil+\lceil -x\rceil=0}, otherwise {1}.

Problem 8: If {x} is an integer, {\{ x\}+\{ -x\}=0}, otherwise {1}.

Euler Equation

Euler’s identity is regarded as the most beautiful equation in mathematics, since it combines five very important numbers {e,\pi,i,0,1}. The identity is:

\displaystyle \begin{array}{rcl} e^{i\pi} +1 & = & 0 \end{array}

The identity is a special case of the following general one:

\displaystyle \begin{array}{rcl} e^{ix} & = & \cos x+i\sin x \end{array}

It has many proofs. Here is an elegant one. Let {y=\cos x+i\sin x}. Then

\displaystyle \begin{array}{rcl} \dfrac{dy}{dx} & = &-\sin x+i\cos x\\ & = & i^2\sin x+i\cos x\\ & = & i(\cos x+i\sin x)\\ & = & iy\\ \dfrac{dy}y & = idx \end{array}

Now let’s integrate both sides. As we know {\int \frac{1}x=\ln x} and {\int dx = x}, we have

\displaystyle \begin{array}{rcl} \int \dfrac{dy}y & = & \int idx\\ \ln y & = & ix+C \end{array}

for some constant {C} (since it is indefinite integration). We get

\displaystyle \begin{array}{rcl} e^{ix+C} & = & y\\ & = & \cos x+i\sin x \end{array}

We need to find the value of {C}, so let’s set {x=0}, and we get

\displaystyle \begin{array}{rcl} e^{C} & = & 1 \end{array}

So {C=0} and we have

\displaystyle \begin{array}{rcl} e^{ix} & = & \cos x+i\sin x \end{array}

Set {x=\pi} and we have

\displaystyle \begin{array}{rcl} e^{i\pi} +1 & = & 0 \end{array}

DONE!

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 {n>1} be an integer and {a} be an integer co-prime to {n}. Then there are integers {x,y} with {0<|x|,|y|<\sqrt{n}} so that

\displaystyle \begin{array}{rcl} x & \equiv ay\pmod n \end{array}

Such a solution {(x,y)} is called a small solution sometimes.

Proof: Let {r=\lfloor\sqrt{n}\rfloor} i.e. {r} is the unique integer for which {r^2\leq n<(r+1)^2}. The number of pairs {(x,y)} so that {0\leq x,y\leq r} is {(r+1)^2} which is greater than {n}. Then there must be two different pairs {(x_1,y_1)} and {(x_2,y_2)} so that

\displaystyle \begin{array}{rcl} x_1-ay_1 &\equiv x_2-ay_2\pmod n\\ x_1-x_2 &\equiv a(y_1-y_2)\pmod n \end{array}

Let {x=x_1-x_2} and {y=y_1-y_2}, and we get {x\equiv ay\pmod n}. Now, we need to show that {0<|x|,|y|<r<n}. Certainly, if one of {x,y} is zero, the other is zero as well. If both {x} and {y} are zero, that would mean that two pairs {(x_1,y_1)} and {(x_2,y_2)} are actually same. That is not the case, and so both {x,y} can not be {0}. Therefore, none of {x} or {y} is {0}, and we are done. \Box

Corollary 2: For a prime {p} and an integer {a}, there are integers {x,y} with {0<|x|,|y|<\sqrt{p}} such that

\displaystyle \begin{array}{rcl} a & \equiv xy\pmod p \end{array}

This lemma can be generalized even more with the same proof.
Theorem 3 (Generalization of Thue’s Lemma): Let {\alpha} and {\beta } are two real numbers so that {\alpha\beta \geq p}. Then for an integer {x}, there are integers {a,b} with {0<|a|<\alpha} and {0<|b|<\beta } so that,

\displaystyle \begin{array}{rcl} a & \equiv & xb\pmod p \end{array}

And we can even make this lemma a two dimensional one.
Theorem 4 (Two Dimensional Thue’s Lemma): Let {n\geq2,r=\sqrt{n}} and {a,b,c,d} be arbitrary integers. There exist {w,x,y,z} with at least one of {y,z} non-zero such that

\displaystyle \begin{array}{rcl} 0\leq |w|,|x|,|y|,|z|\leq r\\ w\equiv ay+bz\pmod n\\ x\equiv cy+dz\pmod n \end{array}

2. Applications

First we show an elegant proof of Fermat’s {4n+1} 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): {a} is a quadratic residue of a prime {p} if there exist an integer {x} so that,

\displaystyle \begin{array}{rcl} x^2 & \equiv a\pmod p \end{array}

{a} is a quadratic non-residue if there doesn’t exist any such integer {x} that,

\displaystyle \begin{array}{rcl} x^2 & \equiv a\pmod p \end{array}

Definition 7: Two integers {a} and {b} are co-prime if their greatest common divisor {(a,b)=1}. We denote this by {a\perp b}.

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: {-1} is a quadratic residue of a prime {p} if and only if {p} is of the form {4n+1}.

Theorem 9 (Fermat’s {4n+1} Theorem): Every prime of the form {4n+1} can be written as a bisquare.

Proof: We already know that, for {p\equiv1\pmod4}, there is an {x} so that,

\displaystyle \begin{array}{rcl} x^2 & \equiv-1\pmod p \end{array}

From Thue’s theorem, for such an {x}, there are integers {a,b} with {0<|a|,|b|<\sqrt{p}} so that,

\displaystyle \begin{array}{rcl} a &\equiv xb\pmod p\\ a^2 &\equiv x^2b^2\pmod p\\ &\equiv-b^2\pmod p\\ a^2+b^2&\equiv0\pmod p \end{array}

The last congruence means that {p|a^2+b^2}, so

\displaystyle \begin{array}{rcl} p &\leq a^2+b^2\text { but}\\ a^2+b^2 &< p+p\\ & = 2p \end{array}

Therefore, {a^2+b^2=p} must occur. \Box

In fact, we can use the same technique for generalizing Fermat’s {4n+1} theorem.
Theorem 10: Let {n\in\{-1,-2,-3\}}. If {n} is a quadratic residue of a prime {p}, then there are integers {a,b} so that, {a^2-nb^2=p}.

Proof: We have already proven the case {n=-1}. If {n} is a quadratic residue of {p},

\displaystyle \begin{array}{rcl} x^2\equiv n\pmod p \end{array}

has a solution. Fix the integer {x}, and take {a,b} as in Thue’s lemma so that,

\displaystyle \begin{array}{rcl} a & \equiv xb\pmod p\\ a^2 &\equiv x^2b^2\pmod p\\ &\equiv nb^2\pmod p\\ p & |a^2-nb^2 \end{array}

We make two cases for {n}.

  • {n=-2}. Then {p\leq a^2+2b^2<p+2p=3p}. So, either {a^2+2b^2=p} or {a^2+2b^2=2p}. If it’s the first, we are done. If not, we see that {a} must be even. Assume {a=2a'} and we get {p=b^2+2a'^2}, as desired.
  • Now, {n=-3}, so {p\leq a^2+3b^2<p+3p=4p}. If {a^2+3b^2=2p}, then {a} and {b} are both odd or both even. If both are even, then {2p} is divisible by {4}, a contradiction since {p} is odd. Otherwise, {a} and {b} are both odd.

    \displaystyle \begin{array}{rcl} a^2+3b^2 & \equiv1+3\cdot1\pmod4\\ 2p & \equiv0\pmod4 \end{array}

    Again, contradiction. We are left with the case {a^2+3b^2=3p}. This shows {a} is divisible by {3}. If we take {a=3a'}, we get {p=b^2+3a'^2}.

\Box

Corollary 11: For a prime {p} and an integer {n}, there exists integers {x,y} so that {p} divides {x^2+ny^2} if and only if {-n} is a quadratic residue of {p}.

Proof: Without loss of generality, we can take {x} and {y} to be co-prime and {n} not divisible by {p}. First assume, {p|x^2+ny^2}, then {y} must be co-prime to {p}. Therefore, {y} has an inverse modulo {p}, assume {ay\equiv1\pmod p}.

\displaystyle \begin{array}{rcl} a^2y^2 &\equiv1\pmod p\\ p & |a^2x^2+na^2y^2\\ p & |a^2x^2+n\\ (ax)^2&\equiv-n\pmod p \end{array}

For the only if portion, we have {-n} is a quadratic residue of {p}, let {k^2\equiv-n\pmod p}. Clearly, {\gcd(k,p)=1} otherwise {p} will divide {n}. From Thue’s lemma, there are integers {x,y} with

\displaystyle \begin{array}{rcl} x & \equiv ky\pmod p\\ x^2 &\equiv k^2y^2\pmod p\\ &\equiv-ny^2\pmod p\\ p & |x^2+ny^2 \end{array}

\Box

We can use these results to imply the following theorem also.
Theorem 12: For {D\in\{1,2,3\}}, if {n=x^2+Dy^2} for some {x\perp y}, then every divisor {d} of {n} is of the same form.

Proof: Remember the identity:

\displaystyle \begin{array}{rcl} (a^2+Db^2)(c^2+Dd^2)& =(ac-Dbd)^2+D(ad+bc)^2\\ & =(ac+Dbd)^2+D(ad-bc)^2 \end{array}

This means that the product of two numbers of the form {x^2+Dy^2} is of the same form. From theorems above, if {p} is a divisor of {x^2+Dy^2}, then {p=a^2+Db^2} for some {a,b}. The identity clearly says that, if {m=a^2+Db^2}, then any power of {m}, {m^k} is of this form again. Let’s assume that, the prime factorization of {n} is,

\displaystyle \begin{array}{rcl} n & = p_1^{e_1}\cdots p_k^{e_k}\\ & = \prod_{i=1}^{k}p_i^{e_i}\text{ and }\\ d & = \prod_{i=1}^{k}p_i^{f_i}\text{ where }0\leq f_i\leq e_i \end{array}

From the lemma, for any {1\leq i\leq k}, {p_i} is of this form. So, {p_i^{f_i}} is of the same form as well. So, for any divisor {p_1^{f_1}\cdot p_2^{f_2}} is of the same form again. Repeating this upto {p_k^{f_k}} we get that, {p_1^{f_1}\cdots p_k^{f_k}=d} is of the same form again. \Box

Now we prove another theorem that demonstrates the power of Thue’s theorem. We will use the following theorem without proof.
Theorem 13: {-3} is a quadratic residue of {p} if and only if {p} is of the form {3k+1}.

Theorem 14: If {p} is a prime of the form {3k+1}, there are integers {a,b} such that {p=a^2+ab+b^2}.

Proof: Since {p} is of the form {3k+1}, {-3} is a quadratic residue of {p}. Take {y} to be an odd integer for which {p|y^2+3} or,

\displaystyle \begin{array}{rcl} y^2 & \equiv-3\pmod p \end{array}

Such an {y} exists, since {p} is odd. Even if {y} is even, {y\equiv2x+1\pmod p} has a solution. For that {x}, we get,

\displaystyle \begin{array}{rcl} (2x+1)^2 & \equiv-3\pmod p\\ 4x^2+4x+1& \equiv-3\pmod p\\ 4(x^2+x+1)&\equiv0\pmod p\\ x^2+x+1 & \equiv0\pmod p \end{array}

because {p} is odd. From Thue’s theorem, there are integers {a,b} with {0<|a|,|b|<p} such that,

\displaystyle \begin{array}{rcl} a & \equiv xb\pmod p \end{array}

Then we also get

\displaystyle \begin{array}{rcl} a^2+ab+b^2 & = a^2+a\cdot ax+(ax)^2\\ & = a^2(x^2+x+1)\\ & \equiv 0\pmod p \end{array}

Because {p|a^2+ab+b^2}, {p\leq a^2+ab+b^2}. On the other hand,

\displaystyle \begin{array}{rcl} p& \leq a^2+ab+b^2 \\ & < p+p+p\\ & = 3p \end{array}

Either {a^2+ab+b^2=p} or {a^2+ab+b^2=2p}. We can easily check that {a^2+ab+b^2=2p} can not happen (try yourself). \Box

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 {p>5} be a prime so that, {p} divides {k^2+5} for some integer {k}. Show that, there are integers {x,y} such that, {p=x^2+5y^2}.

Theorem 16: If {p} is a prime of the form {8 n -1}, there is at least one prime {q} in the interval {(0,\sqrt{p})} which is a quadratic non-residue of {p}.

Proving these two theorems should be fairly easy. Now we see some applications.
Problem 17: Let {p} be a prime for which there exists a positive integer {a} such that {p} divides {2a^2-1}. Prove that, there exist integers {b} and {c} so that, {p=2b^2-c^2}.

Solution 18: We have {2a^2-1\equiv0\pmod p}. Since we want to bound {2b^2-c^2}, it is obvious, we should find {b,c} so that {p} divides {2b^2-c^2} and then bound it. This is where Thue’s lemma comes in. Fix the integer {a}, which is clearly co-prime to {p}. Then from Thue’s lemma, we there are integers {b,c} with {0<|b|,|c|<\sqrt{p}} so that,

\displaystyle \begin{array}{rcl} b & \equiv ac\pmod p \end{array}

This gives us what we need. Note that,

\displaystyle \begin{array}{rcl} 2b^2-c^2 & \equiv 2(ac)^2-c^2\\ & \equiv c^2(2a^2-1)\\ & \equiv 0\pmod p \end{array}

Thus, {p} divides {2b^2-c^2}, and now we get to use the fact:

\displaystyle \begin{array}{rcl} p\leq 2b^2-c^2 & < 2b^2\\ & < 2p \end{array}

We immediately get that {p=2b^2-c^2}.

Problem 19: Let {n} be an integer. Prove that if the equation {x^2+xy+y^2=n} has a rational solution, then it also has an integer solution.

Problem 20 (Iran Olympiad, {3}rd Round): Let {p} be a prime number. Prove that, there exists integers {x,y} such that {p=2x^2+3y^2} if and only if {p\equiv5,11\pmod{24}}.

Problem 21 (Polish Math Olympiad Problem): Let {S} be a set of all positive integers which can be represented as { a^2 + 5b^2} for some integers { a,b} such that { a\bot b}. Let {p} be a prime number such that { p = 4n + 3} for some integer { n}. Show that if for some positive integer { k} the number { kp} is in {S}, then {2p} is in { S} as well.

Problem 22: Prove that the equation {x^3-x+9=5y^2} has no solution in integers.

বিভাজ্যতা(প্রথম অংশ, বিগিনারদের জন্য)

সংজ্ঞাঃ a|b এর মানে হচ্ছে a দিয়ে b বিভাজ্য, অর্থাৎ b কে a দিয়ে ভাগ করলে ভাগশেষ ০ হয়। এখানে a কে বলে ভাজক(divisor) বা উৎপাদক(factor), এবং b কে বলে a এর গুণিতক(multiple)।

যেমন  9,3 দিয়ে বিভাজ্য। নোটেশন ব্যবহার করে 3|9.

এখন এর কিছু বৈশিষ্ট্য দেখা যাক।

  1. a|b হলে অবশ্যই b\ge a
  2. যদি a|b হয় যাতে করে b এর মান a এর চেয়ে কম, তাহলে b=0 হতে হবে।
  3. a|b হলে \dfrac{b}{a} একটি পূর্ণসংখ্যা হবে যা আসলে এদের ভাগফল। ধরি ভাগফল হচ্ছে k. তার মানে এমন পূর্ণসংখ্যা k থাকবে যাতে b=ak. তার মানে প্রত্যেকটা বিভাজ্যতা আসলে একটা সমীকরণ বলা যায়। শুধু আমরা সুবিধার জন্য এভাবে ব্যবহার করি। নয়তো সরাসরি ও করা যাবে, কিন্তু শুধু শুধু কষ্ট করা লাগবে।
  4. a|b,a|c\Longrightarrow a|b-c
  5. a|b\Longrightarrow a|b+aq .
  6. a|b,a|c হলে যে কোন পূর্ণসংখ্যা x,y এর জন্য a|bx+cy. কারণ, b=ak, c=al লেখা যায়। তখন bx+cy=a(kx+ly) যা b দিয়ে বিভাজ্য। এটা খুবই গুরুত্বপূর্ণ একটা বৈশিষ্ট্য। সমস্যা সমাধান করতে গেলে দেখা যাবে।

আপাতত সমস্যায় চলে যাই।

১। এমন সব ধনাত্মক পূর্ণসংখ্যা n বের কর যাতে করে n|2n+3.

সমাধানঃ বিভাজ্যতার ডানে আছে n যা আমরা জানি না। তাই আমাদের পরম দায়িত্ব হচ্ছে একে সরানো। একে সরানোর জন্যই উপরের সাহায্য লাগবে। কিভাবে?

দেখো, ডানে n এর সহগ হচ্ছে 2. এখন আমরা তো চাইলেই n এর যে কোন গুণিতক বাদ দিতে পারি। এজন্য আমাদের লাগবে n|2n. এখন n কে চাইলেই বাদ দেওয়া যায়। কারণ n|(2n+3)-(2n)\Longrightarrow n|3. তার মানে 3 এর প্রত্যেকটি ভাজকের জন্য এক-একটি করে সমাধান পাওয়া যাবে। অর্থাৎ n=1,3

২। xy=12 এই সমীকরণের কয়টি সমাধান থাকবে?

সমাধানঃ খেয়াল করে দেখো যে এখানে x, 12 এর কোন ভাজক হলে, প্রত্যেকটি ভাজকের জন্যই একটি করে y মানে একটি করে সমাধান পাওয়া যাবে। তার মানে সমাধান সংখ্যা হবে 12 এর ভাজকসংখ্যা। এখন, ১২ এর ভাজক হচ্ছে ১,২,৩,৪,৬,১২ এই ছয়টি। তাই এই সমীকরণের সমাধানের সংখ্যা ও ছয়টি। আমরা সমীকরণকে এইভাবে ও লিখতে পারি x|n.

এখন থেকে আমরা কোন সংখ্যা n এর ভাজক সংখ্যা(number of divisor) প্রকাশ করবো \tau(n) দিয়ে। মানে উপরের উদাহরণে \tau(12)=6. এই সমস্যা থেকে আরো একটা দরকারী কিছু শিখা যায়। যদি কোন সমীকরণের সমাধান সংখ্যা বের করতে বলা হয়, তাহলে সবার আগে ঐটাকে কোনভাবে একটা এই ধরনের সমীকরণের সমাধানের সংখ্যা যদি বের করতে বলা হয় তাহলে সবার আগে চিন্তা করা দরকার তাকে কোনভাবে এই ধরনের বিভাজ্যতা বানানো যায় কিনা। তাহলেই সেটা কোন কিছুর ভাজকসংখ্যা হবে।

সমস্যাঃ এমন সব ধনাত্মক পূর্ণসংখ্যা n বের কর যাতে 2n+1|6n-4.

সমাধানঃ এবার দেখো ডানে n এর সহগ 6 আর বামে 2. তাই বামে ৩ দিয়ে গুন করে আগে ৬ বানিয়ে নিতে হবে। 2n+1|3(2n+1)=6n+3. আবার বিয়োগ, 2n+1|6n+3-(6n-4)=7. তাহলে 2n+1=1\text{ or }7. কিন্তু যেহেতু n\in\mathbb N,n\ge1 তাই 2n+1\ge3. সেজন্য 2n+1=7\implies n=3.

আচ্ছা, একটা ব্যাপার কি পরিষ্কার? আমরা আসলে কি করতে চাই? n এর মান যেহেতু জানি না, তাই ডান পাশ থেকে যদি কোন ভাবে n কে সরানো যায়, তাহলে আমরা একটা সাংখ্যিক মান পেয়ে যাই। তখন আমরা সমাধান করতে পারবো। তাই দুইপাশে n এর সহগ সমান করা দরকার। তার মানে একপাশে যদি সহগ থাকে a আর অন্য পাশে থাকে b তাহলে আমাদের আনতে হবে a আর b এর লসাগু, অথবা তাদের গুণফল যাতে পরে তাদের কাটা যায়।