Linked Questions

32
votes
10answers
9k views

Is there possibly a largest prime number?

Prime numbers are numbers with no factors other than one and itself. Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of "...
29
votes
10answers
5k views

Proving $\sqrt 3$ is irrational.

There is a very simple proof by means of divisibility that $\sqrt 2$ is irrational. I have to prove that $\sqrt 3$ is irrational too, as a homework. I have done it as follows, ad absurdum: Suppose $$\...
15
votes
2answers
15k views

In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc ...
4
votes
2answers
860 views

Approximation of irrationals by fractions

If $\alpha$ is an irrational, and I'm trying to judge the suitability of of a rational $p/q$ as its approximation by the error $\Delta = |\alpha - p/q|$. For a given denominator $q$, I am finding a $p$...
3
votes
3answers
1k views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
11
votes
3answers
683 views

Prove that there exists infinitely many positive integers $n$ such that $\sin^2{(na)}+\sin^2{(nb)}\le \frac{2\pi^2}{n}$

Can anyone please help me with the following proof: Prove that there exists infinitely many positive integers, $n$, such that $$\sin^2{(na)}+\sin^2{(nb)}\le \dfrac{2\pi^2}{n}\quad a,b\in \Bbb R$$
4
votes
2answers
545 views

Fundamental unit in the ring of integers $\mathbb Z[\frac{1+\sqrt{141}}{2}]$

Find a fundamental unit in the ring of integers $\mathbb Z[\frac{1+\sqrt{141}}{2}]$ of $\mathbb Q(\sqrt{141})$ I have different corollaries for different numbers, the most appropriate for $141$ is ...
4
votes
2answers
945 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
6
votes
1answer
267 views

An application of the pigeonhole principle in analysis

The pigeonhole principle is stated here. I found in a book the following application: We can obtain the nature of the series $\sum \frac 1{n^2\sin^2(n)}$ from the pigeonhole principle. The issue ...
3
votes
5answers
156 views

Set of the form $m + n \alpha $ is bounded by $0$?

Let $\alpha >0 $ be an irrational number and consider $$ A = \{ m + n \alpha : m + \alpha n > 0 , \; \; \; m,n \in \mathbb{Z} \} $$ Obviously, $A$ is bounded below by $0$. But, how can I show ...
5
votes
1answer
459 views

Pell's Equation and the Pigeon Hole Principle

David Speyer gave a beautiful application of the pigeon hole principle here to show that Pell's equation $$x^2-Dy^2=1$$ has infinitely many integral solutions. I was wondering if anybody knows the ...
1
vote
2answers
492 views

Prove that the language $\{ww \mid w \in \{a,b\}^*\}$ is not FA (Finite Automata) recognisable.

Hint: Assume that $|xy| \le k$ in the pumping lemma. I have no idea where to begin for this. Any help would be much appreciated.
13
votes
1answer
359 views

Proving that the number of integer solutions of $x^2-Ny^2=1$ is infinite

I am trying to prove that the number of integer solutions of $x^2-Ny^2=1$ is infinite whenever N is a squarefree integer. For this I define norm of $a+b\sqrt N=a^2-Nb^2$. Now I prove that $a+b \sqrt ...
2
votes
1answer
457 views

Pigeonhole principle to prove division

Here's a little question that we were shown in class: Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$. Prove that there are two elements of $A$ such that one is a ...
1
vote
1answer
137 views

prove existence of integers $a,q$ which satisfy the following inequality

Let $x \in \mathbb{R}$ and integer $Q \geq 1$. Prove: there exist integers $a$ and $1 \leq q \leq Q$ such that $|x - \frac aq | < \frac 1{qQ} $ any help would be appreciated!

15 30 50 per page