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.