Homework 1
Unique Factorization in \(\mathbb{Z}\) and Congruences
Instructions
For each problem, please write a complete argument, not only intermediate calculations. Answers without justification may receive zero credit. Collaboration is encouraged, but you must write your own final solutions independently.
1 Divisibility is transitive. Prove directly from the definition of divisibility that if \(a\mid b\) and \(b\mid c\), then \(a\mid c\).
2 Division algorithm. The division algorithm asserts that for any integers \(a,b\in\mathbb{Z}\) with \(b\ne0\), there exist unique integers \(q,r\in\mathbb{Z}\) such that
\[ a=qb+r,\qquad 0\le r<|b|. \]
(1) Let \(x\) be a real number. Denote by \(m\) and \(n\) the greatest integer not exceeding \(x\) and the least integer no less than \(x\), respectively. Show that
\[ x-1<m\le x\le n<x+1. \]
(2) Prove the existence part of the division algorithm.Hint
Take \(q\) to be the greatest integer not exceeding \(a/b\) when \(b>0\) and the least integer no less than \(a/b\) when \(b<0\).(3) Prove the uniqueness part of the division algorithm: if there are \(q_1,q_2,r_1,r_2\in\mathbb{Z}\) such that
\[ \begin{aligned} a &= q_1b+r_1,\qquad 0\le r_1<|b|,\\ a &= q_2b+r_2,\qquad 0\le r_2<|b|, \end{aligned} \]
then \(q_1=q_2\) and \(r_1=r_2\).
3 Definition of ideal. Show that for any \(a,b\in\mathbb{Z}\), the set
\[ I_{a,b}=\{ax+by:x,y\in\mathbb{Z}\} \]
is an ideal of \(\mathbb{Z}\).
4 Multiplying congruences. Use the definition of congruence to show that if \(a_1\equiv b_1\pmod{m}\) and \(a_2\equiv b_2\pmod{m}\), then \(a_1a_2\equiv b_1b_2\pmod{m}\).
5 A divisibility test. Prove that a nonzero integer is divisible by \(3\) if and only if the sum of its base-10 decimal digits is divisible by \(3\). What can you say about divisibility by \(11\)?
Hint
Use \(10\equiv1\pmod3\) and write the integer in its base-10 expansion.6 Euclidean algorithm.
(1) Use Euclidean algorithm to compute \(\gcd(2026,748)\).
(2) Express the gcd as \(2026x+748y\) for integers \(x,y\).Hint
Substitute the remainders backwards.Hint
Start by solving \(37x+101y=1\) to get a value of \(x\).7 Linear equations. Determine whether \(84x+126y=30\) has an integer solution \((x,y)\in\mathbb{Z}^2\). If it does, find all integer solutions; if it does not, prove impossibility.
8 A structural gcd identity. Let \(m,n\in\mathbb{Z}\), not both equal to zero. Prove that for every integer \(k\) we have
\[\gcd(m,n+km)=\gcd(m,n).\]
This identity can be used to compute the greatest common divisors via successive subtraction until the numbers become manageable. For instance, \[\gcd(531,225)=\gcd(306,225)=\gcd(81,225)=\gcd(81,144)=\gcd(81,63)=9.\] The idea involved here is the same as in Euclidean algorithm.
Optional challenge
9 Modulo powers of 2.
Show that the square of every odd integer is congruent to \(1\) modulo \(8\).
Show by induction that for any odd integer \(a\) and any integer \(n\ge3\), we have
\[ a^{2^{n-2}}\equiv1\pmod{2^n}. \]