I'm trying to prove that $\sqrt{x} \leq 2^{\pi(x)}$ for all $x \geq 0 \in \mathbb R$, where $\pi$ is the prime-counting function. To do this, I note that $2^{\pi(x)}$ may be viewed as the number of different products we may produce from the $\pi(x)$ different primes that are at most $x$; since in each such product the power of each prime is at most one, each product is squarefree. Since by convention 1 is squarefree, then $2^{\pi(x)}$ is precisely the number of squarefree numbers at most $x$.  Furthermore, $\lceil \sqrt{x}\rceil = \left|\{n^2 : n^2 \leq x\}\right|$ (with equality if and only if $x$ is a square), so that proving that $\sqrt{x} \leq 2^{\pi(x)}$ is equivalent to showing that there is an injection $$f : \{n^2 \in \mathbb Z : n^2 \leq x\} \to \{n : n \leq x \text{ and $n$ is squarefree}\}.$$ Supposing that for any integer $n \geq 1$ there is some squarefree number $k$ such that $n^2 &lt; k &lt; (n + 1)^2$, then producing such an injective function is trivial. But I do not see a way to prove this last claim: that between any two squares there is a squarefree number. How does one prove this statement?
123211
Is there a  squarefree ( with two prime divisors) betweem any two consecutive squares?
50979
Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.      Proof. The proof is by induction on the numbers of elements of $X$.      For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.      Now the induction step. Suppose $|X|=n$; by the induction hypotesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$      From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.  The construction of a new set $S$ is the union of the old set with cardinality $n$ and an new element $\{a\}$, therefore the set that do not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element...  Can someone please elucidate?
44142
I'm not sure if this proof is valid or not and could use some feedback.  Let P be the supposition that $2^n \le 2^{n+1}-2^{n-1} - 1$ for all positive integers n.   Base Case: Let n=1  $2^1 \le 2^2-2^0-1$  $2\le2$   Suppose that P holds true for some positive integer n=k  $$2^{k+1}=2*2^k$$  By inductive hypothesis:  $$2*2^k \le 2(2^{k+1}-2^{k-1}-1)$$  $$2^{k+1} \le 2^{k+2}-2^{k}-2$$   Since we know $2^{k+1} \le 2^{k+2}-2^{k}-2$, we also know $2^{k+1} \le 2^{k+2}-2^{k}-1$ because the former is always smaller.  This proves that: $$2^k \le 2^{k+1}-2^{k-1} - 1\Rightarrow 2^{k+1} \le2^{k+2}-2^{k}-1 $$
53865
For a prime number $p \neq 3$, do we have that$$p = x^2 + xy + y^2$$for some $x$, $y \in \mathbb{Z}$ if and only if$$p \equiv 1 \text{ mod }3?$$I suspect this is true from looking at the example$$7 = 2^2  + 2 \times 1 + 1^2.$$Here is a thought I have so far that might be helpful towards solving this: I know that $$\mathbb{Z}[(1 + \sqrt{-3})/2]$$is a PID. But I am not sure what do from here. Could anybody help?
1779
Page 105 of D. Burton's A First Course in Rings and Ideals reads     It is not difficult to show that if (I'll call them $n$ and $m$ instead of $n_1$ and $n_2$) $n$, $m$ are square free integers, then $\mathbb{Q}(\sqrt{n}) \cong \mathbb{Q}(\sqrt{m})$ if and only if $n=m$.   Well, it is getting difficult for me, any help or would be appreciated.    My progress so far: Suppose $\phi :\mathbb{Q}(\sqrt{n})\to\mathbb{Q}(\sqrt{m})$ is an isomorphism. Then $\phi(u)=u$ for every $u \in \mathbb{Q}$, so that $\phi(\sqrt{n})^2=\phi(n)=n$. If $\phi(\sqrt{n})=a+b\sqrt{m}$ for some $a,b\in\mathbb{Q}$, then $(a+b\sqrt{m})^2=a^2+b^2m + 2ab\sqrt{m}=n$ implies $$a^2+b^2m = n$$ and $$2ab=0.$$  Then $b=0$ cannot happen since that would imply that $\sqrt{n}\in\mathbb{Q}$, where $n$ is a square-free integer. Also $a=b=0$ cannot happen. Hence $a=0$ and we have $$b^2m=n.$$ If $\psi:\mathbb{Q}(\sqrt{n})\to\mathbb{Q}(\sqrt{m})$ were an isomorphism then there would exist some $s\in\mathbb{Q}$ such that $$s^2m=n,$$ then $s=b$ or $s=-b$. Therefore the only isomorphisms from $\mathbb{Q}(\sqrt{n})$ to $\mathbb{Q}(\sqrt{n})$ are $\phi(u+v\sqrt{n})=u+vs\sqrt{m}$ and $\psi(u+v\sqrt{n})=u-vs\sqrt{m}$.    I don't know if there's an easier way and I don't know if I'm in the correct way here. Thanks beforehand :)
118815
I have been given the following question in my homework:      Show that for every $n \in \mathbb{N}$ there are at least ${\log_2log_2 (n-1)}$ primes in $[1,n]$   I think it is related to euclidean and induction but I am having difficulties developing my solution.   Thanks for your help (:
72644
Prove that for $ n \geq 2$, n has at least one prime factor.  I'm trying to use induction. For n = 2, 2 = 1 x 2. For n > 2, n = n x 1, where 1 is a prime factor. Is this sufficient to prove the result? I feel like I may be mistaken here.
70466
Given $x\in\mathbb R_+$ and $m,n\in\mathbb Z_+$, is it true that $$\bigg\lfloor\frac{\lfloor \frac{x}{m}\rfloor}{n}\bigg\rfloor=\bigg\lfloor \frac{x}{mn}\bigg\rfloor?$$    Thanks for at least three different and convincing proofs! I'll use this result  trying to code the prime counting formula from Wikipedia $(2)$:  Given $m$, select $y$ so that  $\sqrt[3]{m}\le y\le\sqrt{m}$ and let $n=\pi(y)$. Then  $(1)\;$ $\pi(m)=\phi(m,n)+n-1-P_2(m,n)$, where  $(2)\;$ $\displaystyle \phi(m,n)=\phi(m,n-1)-\phi\Big(\frac{m}{p_n},n-1\Big)$,  $\;\phi(m,0)=\lfloor{m}\rfloor$ and  $(3)\;$ $\displaystyle P_2(m,n)=\sum_{y&lt;p\le\sqrt{m}} \Big(\pi\Big(\frac{m}{p}\Big)-\pi(p)+1\Big)$, $\;p$ is a prime.
22596
Let $m$ be a natural number. Define $f(m) = m + \lfloor\sqrt{m}\rfloor$. Prove that at least one of the number among $m, f(m), f^2(m), \ldots$ is a perfect square. Here $f^k(m)$ denotes the composition of $f$ over itself $k$ times.  I tried the question, but the greatest integer along with square root is creating trouble.
74113
Let $n&gt;1$ be an integer. Prove that $0$ is a radical ideal in $\mathbb{Z}/n\mathbb{Z}$ if and only if $n$ is a product of distinct primes to the ﬁrst power (i.e., $n$ is square free). Deduce that $(n)$ is a radical of $\mathbb{Z}$ if and only if $n$ is a product of distinct primes in $\mathbb{Z}$.  I don't really get it. For example, $8$ is not a square-free integer; so take $\mathbb{Z}/8\mathbb{Z}$. Why is $0$ not a radical ideal in this ring but is in $\mathbb{Z}/6\mathbb{Z}$?
51490
I stumbled on the following inequality: For all $n\geq 1,$ $$2\sqrt{n+1}-2\sqrt{n}&lt;\frac{1}{\sqrt{n}}&lt;2\sqrt{n}-2\sqrt{n-1}.$$ However I cannot find the proof of this anywhere. Any ideas how to proceed?  Edit: I posted a follow-up question about generalizations of this inequality here:
104991
I could use some help with proving this inequality:  $$\left|\,x_1\,\right|+\left|\,x_2\,\right|+\cdots+\left|\,x_p\,\right|\leq\sqrt{p}\sqrt{x^2_1+x^2_2+\cdots+x^2_p}$$ for all natural numbers p.    Aside from demonstrating the truth of the statement itself, apparently $\sqrt{p}$ is the smallest possible value by which the right hand side square root expression must be multiplied by in order for the statement to be true.  I've tried various ways of doing this, and I've tried to steer clear of induction because I'm not sure that's what the exercise was designed for (from Bartle's Elements of Real Analysis), but the best I've been able to come up with is proving that the statement is true when the right hand side square root expression is multiplied by p, which seems pretty obvious anyway.  I feel like I'm staring directly at the answer and still can't see it.  Any help would be appreciated.
10900
For every $ N \in \mathbb Z$ there exists an integer $n$ such that $ \sqrt N \in \mathbb Q(\zeta_n)$.   I am struggling where to start this question, please suggest me few hints.
32031
I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How would one prove this? One way is to use Cauchy-Davenport, but I don't think that this is the simplest solution.
120607
This is a proof from a book on number theory I'm reading. I'm having a hard time following. I think there's a variable here that means two different things at two different times...  Theorem:  If n is a positive integer and p is a prime, then $p^e \vert\vert n!$, where $e=\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \dots + \lfloor\frac{n}{p^r}\rfloor$ and r is determined by n by the inequality $p^r \le n &lt;p^{r+1}$  Proof:  For a given integer k, the multiples of $p^k$ that do not exceed  n are $p^k, 2p^k, \cdots, qp^k$ , where q is the largest integer such that $qp^k \le n$. But this says that q is the largest integer not exceeding $n/p^k$, so that  $q= \lfloor n/p^k \rfloor$. Thus, $\lfloor n/p^k\rfloor$ gives the number of positive multiples of $p^k$ that do not exceed n.     Interlude:      I understand the proof so far. We've simply chosen some power of p   and shown that $\lfloor n/p^k \rfloor$ is the largest integer that we can multiply by $p^k$ and stay under n. Here's where I start to get confused.   Now, if $1 \le m \le n$, then $m=qp^k$ with $(q,p) = 1, 0 \le k \le r$, and m contributes precisely k to the total exponent e with which p appears in the canonical representation of n!     Interlude 2:      How exactly does $m=qp^k$ follow from $1 \le m \le n$? Also, this q seems to mean something other than $\lfloor n/p^k\rfloor$ since we seem to be considering the set of all numbers less than or equal to n and greater than or equal to 1 that have the form $m=qp^k$?   Moreover, m is counted precisely k times by the sum  $\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \dots + \lfloor\frac{n}{p^r}\rfloor$,   once as a multiple of p, once as a multiple of $p^2$, ... , once as a multiple of $p^k$, and no more. Of course, if $k=0$, then m is not counted in the sum. Therefore, the sum above accounts exactly for the contribution of each m between 1 and n to the exponent e as claimed.     Interlude 3:      What exactly is meant here by counted? I really don't understand the last part of this proof at all...
599
This an interesting problem my friend has been working on for a while now (I just saw it an hour ago, but could not come up with anything substantial besides some PMI attempts).  Here's the full problem:  Let $x_{1}, x_{2}, x_{3}, \cdots x_{y}$ be all the primes that are less than a given $n&gt;1,n \in \mathbb{N}$.   Prove that $$x_{1}x_{2}x_{3}\cdots x_{y} &lt; 4^n$$  Any ideas very much appreciated!
27251
Let $D$ be a squarefree integer. I am trying to prove that $\mathbb Q[\sqrt D]$ is contained in a Galois extension of $\mathbb Q$ with Galois group $\mathbb Z/4$ if and only if $D$ is the sum of two squares, $D = a^2 + b^2$ with $a,b\in \mathbb Q$.   The hint in the exercise in Dummit and Foote suggests considering the extension $\mathbb Q[\sqrt{s + s\sqrt D}]$ for the forward direction. However, I am unsure how to show that this extension is Galois, much less that its Galois group is cyclic of order 4.   For the reverse direction, I expressed the given Galois extension as $\mathbb Q[\sqrt{a+b\sqrt D}]$ for some $a,b\in \mathbb Q$. I showed that this extension has $\mathbb Q[\sqrt{c^2 - d^2 D}]$ as a subfield for some $c,d \in \mathbb Q$. From this, I deduced that the $\sqrt D$ and $\sqrt{c^2 - d^2 D}$ generate the same extension, so $\sqrt D = x \sqrt{c^2 - d^2 D}$ for some $x$, and hence that $D = \frac{x^2 c^2}{1 + x^2 d^2} $. It seems that there should be a way to decompose this as a sum of two squares, but I did not see how.   I did not tag this as homework as I am studying it independently.