The notion of an ideal of $\mathbb{Z}$ is a non-empty set of integers that is closed under addition, and closed under multiplication by an arbitrary integer. Let $I$ be a non-empty set of integers that is closed under addition (i.e., $a + b \in I$ for all $a, b \in I$ ). Show that $I$ is an ideal if and only if $-a \in I$ for all $a \in I$.

== Attempt ==

$\implies$

If $I$ is an ideal, clearly $-a \in I$, as $a \cdot (-1) \in I$, picking -1 as an arbitrary integer.

$\impliedby$

Given $I$ is closed under addition, for all $a \in I, a + a = 2a \in I, 2a + a = 3a \in I$, etc. Clearly, if $-a \in I, a\mathbb{Z} \subseteq I$. In other words, if $-a \in I, I$ becomes closed under multiplication by an arbitrary integer.

$\Box$

Division with remainder property:

Let $a,b \in \mathbb{Z}$ with $b > 0$. Then there exist unique $q,r \in \mathbb{Z}$ such that $a = bq + r$ and $0 \le r < b$.

Generalized division with remainder property:

Let $a,b \in \mathbb{Z}$ with $b > 0$, and let $x \in \mathbb{R}$. Then there exist unique $q, r \in \mathbb{Z}$ such that $a = bq + r$ and $r \in [x,\ x + b)$.

Show that the generalized division with remainder property also holds for the interval $(x,\ x + b]$. Does it hold in general for the intervals $[x,\ x + b]$ or $(x,\ x + b)$ ?

== Attempt ==

Consider the interval $(x,\ x + b]$, which contains exactly $b$ integers, namely $\lfloor x \rfloor + 1,\ ... , \lfloor x \rfloor + b$. Applying the division with remainder property with $a - (\lfloor x \rfloor + 1)$ in place of $a$:

$$\begin{aligned} a - (\lfloor x \rfloor + 1) &= bq + r \\ a &= bq + r + \lfloor x \rfloor + 1 \\ \end{aligned}$$

Let $r' = r + \lfloor x \rfloor + 1$. Given $r \in [0,\ b)$,

$$\begin{aligned} r &\in \{0,\ ...,\ b - 1\} \\ r' &\in \{\lfloor x \rfloor + 1,\ ..., \lfloor x \rfloor + 1 + b - 1\} = \{\lfloor x \rfloor + 1,\ ..., \lfloor x \rfloor + b\} \\ r' &\in (x,\ x + b] \end{aligned}$$

In other words, the generalized division with remainder property holds for the interval $(x,\ x + b]$.

Consider the interval $[x,\ x + b]$, which contains integers:

$$\begin{aligned} \{ \lceil x \rceil,\ ..., \lceil x \rceil + b - 1, \lfloor x \rfloor + b\} \end{aligned}$$

In particular, when $x$ is an integer, this set will contain exactly $b + 1$ integers, and therefore the interval $[x,\ x + b]$ does not hold in general. (It would hold, however, in the special case when x is not an integer, since then the set would contain exactly $b$ integers. Do you see why ?)

Similarly, consider the interval $(x,\ x + b)$, which contains integers:

$$\begin{aligned} \{ \lfloor x \rfloor + 1,\ ..., \lfloor x \rfloor + b - 1, \lceil x \rceil + b - 1 \} \end{aligned}$$

In particular, when $x$ is an integer, this set will contain exactly $b - 1$ integers, and therefore the interval $(x,\ x + b)$ does not hold in general. (It would hold, however, in the special case when x is not an integer, since then the set would contain exactly $b$ integers. Do you see why ?)

$\Box$

Given ($a$ mod $b$) is defined to be $a - b \lfloor \frac{a}{b} \rfloor$. Let $a,b \in \mathbb{Z}$ with $b < 0$. Show that ($a$ mod $b$) $\in (b,0]$.

== Attempt ==

First, $\lfloor \frac{a}{b} \rfloor$ is a unique integer $m$ such that $m \le \frac{a}{b} \lt m + 1$. Equivalently, $\frac{a}{b} = m + \epsilon$ for some $\epsilon \in [0,1)$.

$$\begin{aligned} a \text{ mod } b &= a - b \lfloor \frac{a}{b} \rfloor \\ &= a - bm \\ &= b(m + \epsilon) - bm \\ &= b\epsilon \end{aligned}$$

Knowing that

$$\begin{aligned} 0 &\le \epsilon < 1 \text{, and given } b < 0 \\ 0 &\ge b\epsilon > b \\ 0 &\ge (a \text{ mod } b) > b \\ \end{aligned}$$

$\Box$

Let $m$ be a positive integer. Show that for every real number $x \ge 1$, the number of multiples of $m$ in the interval $[1, x]$ is $\lfloor \frac{x}{m} \rfloor$; in particular, for every integer $n \ge 1$, the number of multiples of $m$ among $1, ..., n$ is $\lfloor \frac{n}{m} \rfloor$.

== Attempt ==

First, every real number $x$ can be formulated as the sum of an integer and an $\epsilon \in \mathbb{R} \text{ where } 0 \le \epsilon \lt 1$. Using the "division with remainder property" (which says for every $a, b \in \mathbb{Z}$ with $b > 0$, there exist unique $q, r \in \mathbb{Z}$ such that $a = b \cdot q + r$ and $0 \le r < b$), there exist $q,r \in \mathbb{Z}$ such that:

$$\begin{aligned} x = q \cdot m + r + \epsilon \end{aligned}$$

where $q \ge 0$ and $0 \le r < m$

Obviously, $q$ is the number of multiples of $m$ in the interval $[1, x]$. To find $q$, we can start with dividing both sides by $m$:

$$\begin{aligned} \frac{x}{m} &= q + \frac{r + \epsilon}{m} \\ \lfloor \frac{x}{m} \rfloor &= \lfloor q + \frac{r + \epsilon}{m} \rfloor \\ \end{aligned}$$

Observe $0 \le r + \epsilon < m$, so

$$\begin{aligned} \lfloor \frac{x}{m} \rfloor &= q \\ \end{aligned}$$

Since every integer $n$ is also a real number, the second statement is obviously true by substituting $x$ by $n$ in the first statement.

$\Box$

Let n be a composite integer. Show that there exists a prime p dividing n, with $p \le n^\frac{1}{2}$

== Attempt ==

Given n is composite, there exists $a, b \in \mathbb{N}$ such that:

$$\begin{aligned} a \cdot b &= n \end{aligned}$$

Let's suppose $a <= b$.

If a = b, $a = b = \sqrt{n}$. So the prime p clearly exists.

If a < b,

$$\begin{aligned} a = \frac{\sqrt{n}}{b} \cdot \sqrt{n} \end{aligned}$$

Given $a \not = b \not = \sqrt{n}$, observe that$\sqrt{n} < b$, or else $a > \sqrt{n} > b$, which contradicts the assumption that a < b. This means $a < \sqrt{n}$. So such prime p would also exist.

$\Box$

This is equivalent to show that:

$$\begin{aligned} (\forall \epsilon > 0)(\exists n \in \mathbb{N})(\forall m \ge n)\big[ \space \big\vert \space (\frac{n}{n+1})^2 -1 \space \big\vert < \epsilon \space \big] \end{aligned}$$

Given $\epsilon, 2 > 0$, by the Archimedean property (which says that if $x,y \in \mathbb{R}$ and $x,y > 0$,there is an $n \in \mathbb{N}$ such that $n \cdot x > y$), there is an $n \in \mathbb{N}$ such that:

$$\begin{aligned} (n+1) \cdot \epsilon &> 2 \\ \epsilon &> \frac{2}{n+1} \end{aligned}$$

Consider for all $m \ge n$:

$$\begin{aligned} \big\vert \frac{m^2}{(m+1)^2} - 1 \big\vert = 1 - \frac{m^2}{(m+1)^2} = \frac{2m + 1}{(m+1)^2} \le \frac{2n+1}{(n+1)^2} = \frac{2(n+1) - 1}{(n+1)^2} < \frac{2}{n+1} < \epsilon \end{aligned}$$

$\Box$

# http://stat.ethz.ch/R-manual/R-devel/library/graphics/html/abline.html
# http://stat.ethz.ch/R-manual/R-devel/library/graphics/html/plot.html

# Set up coordinate system
plot(c(-2,3), c(-1,5), type="n", xlab="x", ylab="y", main="y = 2x + 1")
# Set up the x- and y-axis
abline(h=0, v=0, col="gray60")
# Set up a grid
abline(h = -1:5, v = -2:3, col = "lightgray", lty=3)
# Draw a line with slope=2 and y-intercept=1
abline(b=2, a=1, col="red")

# Some references
# http://octave.sourceforge.net/octave/function/text.html
# http://en.wikibooks.org/wiki/Octave_Programming_Tutorial/Plotting
# http://math-blog.com/2011/04/25/plotting-and-graphics-in-octave/
x = [1:0.5:3]
y=x.^2*3
plot(x,y,'-@')
title("y=x^2*3")
xlabel("x")
ylabel("y")
text(1.4,8,"(1.5,6.75)")
text(1.9,13,"(2,12)")
text(2.25,19,"(2.5,18.75)")
print -dpng "foo.png"

Let A = {$r \in \mathbb{Q} \space | \space r > 0 \land r^2 > 3$}. Show that A has a lower bound in $\mathbb{Q}$ but no greatest lower bound in $\mathbb{Q}$. Give all details of the proof.

== Attempt ==

To show that A has a lower bound in $\mathbb{Q}$ is trivial. Clearly, zero is a lower bound of A in $\mathbb{Q}$, as 0 < r for all r in A, and 0 is rational.

Let's assume A has a greatest lower bound x in $\mathbb{Q}$. There are then only three possibilities:

$$\begin{aligned} Case \space 1: \space x^2 & = 3 \\ Case \space 2: \space x^2 & > 3 \\ Case \space 3: \space x^2 & < 3 \end{aligned}$$

Case 1: $x^2 = 3$

The first case is obviously not possible, since $\sqrt{3}$ is irrational. See proof here.

Case 2: $x^2 > 3$

For the second case, suppose

$$\begin{aligned} x & = \frac{p}{q} \space where \space p,q \in \mathbb{N} \space and \space x^2 > 3 \end{aligned}$$

So

$$\begin{aligned} p^2 & > 3q^2 \end{aligned}$$

Let's consider the rational number

$$\begin{aligned} \frac{n^2}{2n+1} \space where \space n \in \mathbb{N} \end{aligned}$$

which increases without bound as n increases. In particular, we can always pick a large enough n so that

$$\begin{aligned} \frac{n^2}{2n+1} & > \frac{3q^2}{p^2 - 3q^2} \\ n^2p^2 - 3n^2q^2 & > 6q^2n + 3q^2 \\ n^2p^2 & > 3q^2(n + 2n + 1) \\ n^2p^2 & > 3q^2(n + 1)^2 \\ \frac{n^2}{(n + 1)^2} \cdot \frac{p^2}{q^2} & > 3 \end{aligned}$$

Let

$$\begin{aligned} y = \frac{n}{(n + 1)} \cdot \frac{p}{q} \end{aligned}$$

Since $n < n + 1$,

$$\begin{aligned} \frac{p^2}{q^2} & > \frac{n^2}{(n + 1)^2} \cdot \frac{p^2}{q^2} > 3 \\ x^2 & > y^2 > 3 \end{aligned}$$

This means y is an element of A but less than x, which contradicts the assumption that x is a lower bound of A in $\mathbb{Q}$ ! So the supposition that $x^2 > 3$ must be false.

Case 3: $x^2 < 3$

For the third case, suppose

$$\begin{aligned} x & = \frac{p}{q} \space where \space p,q \in \mathbb{N} \space and \space x^2 < 3 \end{aligned}$$

So

$$\begin{aligned} p^2 & < 3q^2 \end{aligned}$$

Let's consider the rational number

$$\begin{aligned} \frac{n^2}{2n+1} \space where \space n \in \mathbb{N} \end{aligned}$$

which increases without bound as n increases. In particular, we can always pick a large enough n so that

$$\begin{aligned} \frac{n^2}{2n+1} & > \frac{p^2}{3q^2 - p^2} \\ 3n^2q^2 - n^2p^2 & > 2p^2n + p^2 \\ 3n^2q^2 & > p^2(n + 2n + 1) \\ 3n^2q^2 & > p^2(n + 1)^2 \\ 3 & > \frac{p^2}{q^2} \cdot \frac{(n + 1)^2}{n^2} \end{aligned}$$

Let

$$\begin{aligned} y = \frac{p}{q} \cdot \frac{(n + 1)}{n} \end{aligned}$$

Since $n < n + 1$,

$$\begin{aligned} 3 & > \frac{p^2}{q^2} \cdot \frac{(n + 1)^2}{n^2} > \frac{p^2}{q^2} \\ 3 & > y^2 > x^2 \end{aligned}$$

This means y is a lower bound of A in $\mathbb{Q}$ but greater than x, which contradicts the assumption that x is the greatest lower bound of A in $\mathbb{Q}$ ! So the supposition that $x^2 < 3$ must be false.

As shown in all cases above, it is not possible for A to have a greatest lower bound in $\mathbb{Q}$. This completes the proof.

Assuming QSTK has been installed

Sublime Text 2

Edit the Sublime's Python build file at:

  ~/Library/Application Support/Sublime Text 2/Packages/Python/Python.sublime-build

adding the QSTK environment variables. The file would then end up containing something like:

{
    "cmd": ["python", "-u", "$file"],
    "file_regex": "^[ ]*File \"(...*?)\", line ([0-9]*)",
    "selector": "source.python",

    "env":
    {
        "PATH": "/opt/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/Users/upune/QSTK/Bin",
        "PYTHONPATH": ":/Users/upune/QSTK:/Users/upune/QSTK/Bin",
        "QS": "/Users/upune/QSTK",
        "QSDATA": "/Users/upune/QSTK/QSData",
        "HOSTNAME": "5855pns93223.nag.nznmba.com",
        "QSDATAPROCESSED": "/Users/upune/QSTK/QSData/Processed",
        "QSDATATMP": "/Users/upune/QSTK/QSData/Tmp",
        "QSBIN": "/Users/upune/QSTK/Bin",
        "QSSCRATCH": "/Users/upune/QSTK/QSData/Scratch",
        "CACHESTALLTIME": "12"
    }
}

The environment variables that need to be defined can be found in the file:

    ~/QSTK/local.sh 

Now one can execute those Python scripts under

    ~/QSTK/Exampls/Basic/

with the usual Command-B shortcut key in Sublime Text 2.

TextMate

In TextMate, however, these environment variables would need to be added at

    TextMate > Preferences > Shell Variables

The Python scripts can then be executed with the usual Command-R shortcut key in TextMate.