Let $a,b,n \in \mathbb{Z}$ with $n > 0$ and $a \equiv b \pmod n$. Show that $gcd(a, n) = gcd(b, n)$.

Given $a \equiv b \pmod n$,

$\mspace20pt$ $a - b = y \cdot n \mspace10pt$ for some $y \in \mathbb{Z}$

Observe $gcd(a, n)$ divides both the left hand side and right hand side. Therefore, $gcd(a, n)$ must divide both $b$ and $n$, which means

$\mspace20pt$ $gcd(a, n) \le gcd(b, n)$

Similar argument applies to $gcd(b,n)$ which divides both sides, and therefore,

$\mspace20pt$ $gcd(b, n) \le gcd(a, n)$

Thus, $gcd(a, n) = gcd(b, n)$

$\Box$

# posted by rot13(Unafba Pune) @ 10:57 PM 0 comments

Let $a,b,n \in \mathbb{Z}$ with $n > 0$. Show that $a \equiv b \pmod n$ if and only if $(a \bmod n) = (b \bmod n)$.

Let $r_a = a \bmod n$, and $r_b = b \bmod n$, such that

$$\begin{aligned} a &= x_an + r_a \text{ for some unique } x_a,r_a \in \mathbb{Z} \text{ with } 0 \le r_a \lt n\\ b &= x_bn + r_b \text{ for some unique } x_b,r_b \in \mathbb{Z} \text{ with } 0 \le r_b \lt n \\ a - b &= n(x_a - x_b) + (r_a - r_b) \end{aligned}$$

$\implies$

$\mspace20pt$ Assume $a \equiv b \pmod n$, and note that $0 \le |r_a - r_b| \lt n$. This means $n \mid a - b$, which only makes sense if:

$$\begin{aligned} r_a - r_b &= 0 \\ r_a &= r_b \\ \end{aligned}$$

$\mspace20pt$ Thus $(a \bmod n) = (b \bmod n)$.

$\impliedby$

$\mspace20pt$ The reverse is obvious. Assume $(a \bmod n) = (b \bmod n)$, $r_a - r_b$ must be zero. So

$$\begin{aligned} a - b &= n(x_a - x_b) + (r_a - r_b) \\ a - b &= n(x_a - x_b) \end{aligned}$$

$\mspace20pt$ Thus $a \equiv b \pmod n$.

$\Box$

# posted by rot13(Unafba Pune) @ 11:08 PM 0 comments

Let $S := (R × R) \setminus {(0,0)}$. For $(x,y),(x′,y′) \in S$, let us say $(x, y) ∼ (x′, y′)$ if there exists a real number $\lambda > 0$ such that $(x, y) = (\lambda x′, \lambda y′)$. Show that ∼ is an equivalence relation; moreover, show that each equivalence class contains a unique representative that lies on the unit circle (i.e., the set of points $(x,y)$ such that $x^2 + y^2 = 1$).

First, ~ is obviously reflexive when $\lambda = 1$. Second, $(x, y) = (\lambda x′, \lambda y′)$ implies $(\frac{x}{\lambda},\frac{y}{\lambda}) = (x', y')$, so ~ is symmetric. Third, if $(x, y) = (\lambda_1 x′, \lambda_1 y′)$ and $(x', y') = (\lambda_2 x'', \lambda_2, y'')$, then $(x, y) = (\lambda_1 \lambda_2 x'', \lambda_1 \lambda_2 y'')$, so ~ is transitive. Thus, ~ is an equivalence relation.

To show that each equivalence class contains a unique representative that lies on the unit circle, consider $\lambda = \frac{1}{\sqrt{x^2 + y^2}}$:

$$\begin{aligned} (x_u, y_u) = (\frac{x}{\sqrt{x^2 + y^2}}, \frac{y}{\sqrt{x^2 + y^2}}) \end{aligned}$$

Notice

$$\begin{aligned} x_u^2 + y_u^2 = \frac{x^2}{x^2 + y^2} + \frac{y^2}{x^2 + y^2} = 1 \end{aligned}$$

In other words, $(x_u, y_u)$ is the unique representative that lies on the unit circle for each equivalence class $[(x,y)]$ for all $(x, y) \in S$.

$\Box$

# posted by rot13(Unafba Pune) @ 7:58 PM 0 comments

Let $n$ and $k$ be positive integers, and suppose $x^k = n$ for some $x \in \mathbb{Q}$. Show that $x \in \mathbb{Z}$. In other words, $\sqrt[k]{n}$ is either an integer or is irrational.

Suppose $x \in \mathbb{Q}$,

$$\begin{aligned} x &= \frac{s}{t} \text{ such that } gcd(s,t) = 1 \text{ for some } s \in \mathbb{Z} \text{ and } t \in \mathbb{N} \\ n &= x^k = (\frac{s}{t})^k \\ s^k &= n \cdot t^k \\ \end{aligned}$$

which means $n \mid s^k$.

For each prime $p$, we may define the function $v_p$, mapping non-zero integers to non-negative integers, as follows: for every integer $n \ne 0$, if $n = p^em$, where $p \nmid m$, then $ν_p(n) := e$. We may then write the factorization of $n$ into primes as

$$\begin{aligned} n &= \pm \prod_{p}p^{v_p(n)} \text{ where the product is over all primes }p \end{aligned}$$

From $s^k = n \cdot t^k$,

$$\begin{aligned} \pm \prod_{p}p^{k \cdot v_p(s)} = \pm \prod_{p}p^{v_p(n)} \prod_{p}p^{k \cdot v_p(t)} \\ \end{aligned}$$

Observe that $n \mid s^k \iff v_p(n) \le v_p(s^k) \equiv k \cdot v_p(s)$ for all primes $p$. Thus,

$$\begin{aligned} \prod_{p}p^{k \cdot v_p(s) - v_p(n)} &= \prod_{p}p^{k \cdot v_p(t)} \\ \end{aligned}$$

which shows that if $k \cdot v_p(s) - v_p(n) > 0$ for some prime $p$, $p$ must be a factor of both $s$ and $t$. But this contradicts the fact that $gcd(s, t) = 1$. So the supposition $x \in \mathbb{Q}$ must be false, or $x$ (ie $\sqrt[k]{n}$) must be irrational in such case. On the other hand, if $k \cdot v_p(s) - v_p(n) = 0$ for all prime $p$, $t$ would necessarily be equal to 1, which means $x$ (ie $\sqrt[k]{n}$) must be an integer in such case.

$\Box$

# posted by rot13(Unafba Pune) @ 4:24 PM 0 comments

Let n be an integer. Generalizing Ex 1.11, show that if $\{a_i\}^k_{i=1}$is a pairwise relatively prime family of integers, where each $a_i$ divides $n$, then their product $\prod_{i=1}^ka_i$ also divides $n$.

From Ex 1.11, we know that if $a,b$ are relatively prime integers, each of which divides $n$, then $ab$ divides $n$. Here, if $a_i, a_j,$ and $a_k$ are relatively prime, $a_i \times a_j, a_k$ will also be relatively prime, since none of these terms share any common prime factor. This means not only does $a_i \times a_j, a_k$ divides $n$, so does $a_i \times a_j \times a_k$, as $a_i \times a_j$ and $a_k$ are relatively prime, and each divides n individually. Recursively applying the same logic to the rest of the terms would necessarily mean $\prod_{i=1}^ka_i$ also divides $n$.

# posted by rot13(Unafba Pune) @ 12:46 AM 0 comments

Job $i$ has a length $t_i$ and a deadline $d_i$. The goal is to assign a starting time $s_i$ to each job such that each job is delayed as little as possible. A job $i$ is delayed if the finishing time $f_i > d_i$. The lateness of the job $i$ is $max(0, f_i - d_i)$. Show that the schedule has the least maximum lateness when $\forall{i,j}[s_i < s_j \implies d_i < d_j]$.

Suppose otherwise $i.e.$ given an optimal schedule with the least maximum lateness among all jobs, suppose there exists in this schedule job $i$ and $j$ with $s_i < s_j$ and $d_j < d_i$, and one of the two jobs has the maximum lateness in the schedule.

Case 1: suppose the earlier job $i$ has the maximum lateness in the schedule

Since $d_j < d_i$, the lateness of the next job $j$ must be greater than that of job $i$. A contradiction $i.e.$ case 1 is not possible.

Case 2: suppose job $j$ has the maximum lateness in the schedule

This means:

$$\begin{aligned} t_i - d_i < t_i + S + t_j - d_j \end{aligned}$$

where $S$ is the total delay in processing all the intervening jobs between $i$ and $j$, if any. If we swap the two jobs, we will now have $s_j < s_i$ and the lateness of job $j$ will be decreased by $t_i + S$, whereas the lateness of job $i$ will be increased by $S + t_j$, $i.e.$

$$\begin{aligned} t_i - d_i + (S + t_j) \end{aligned}$$

Comparing this to the maximum lateness before the swap:

$$\begin{aligned} t_i + S + t_j - d_j \end{aligned}$$

since $d_j < d_i$, the resultant increased lateness of job $i$ must be less than the original maximum. Therefore the new schedule has a least maximum lateness no greater than the original. $\Box$

# posted by rot13(Unafba Pune) @ 9:34 PM 0 comments

Let $n$ be an integer. Show that if $a, b$ are relatively prime integers, each of which divides n, then $ab$ divides n.

Since both $a, b$ divides n, there exist integers $u, v$ such that

$$\begin{aligned} au = n \text{ and } bv &= n \end{aligned}$$

Given $a, b$ are relatively prime integers, there exist integers $s, t$ such that

$$\begin{aligned} as + bt &= 1 \\ as \cdot n + bt \cdot n &= n \\ as \cdot bv + bt \cdot au &= n \\ ab \cdot sv + ab \cdot tu &= n \\ \end{aligned}$$

Since $ab$ divides the left hand side, $ab \mid n$. $\Box$

# posted by rot13(Unafba Pune) @ 11:11 AM 0 comments