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