MATH 341 Midterm 2

$\text{ax+by=c has a solution} \iff \thinspace \text{c is a linear combination of a and b} \iff \thinspace \text{c is a multiple of (a,b)}$

$\text{ax+by=c has a solution for all c} \iff \thinspace \text{(a,b)=1} $

$(\widetilde{\text{x} } ,\widetilde{\text{y}}) \thinspace \text{is a solution to a'x+b'y=c’}$

a|c

$\text{Then a=(a,b)a' and b=(a,b)b'} \in \mathbb{Z} \thinspace \text{then (a',b')=1} $

All of the multiples of m.

m|(a-b)

Congruence mod m is an equivalence relation because it satisfies the reflexive, symmetric, and transitive property.

$\text{(1) Reflexive Property:} \thinspace \text{a} \equiv \text{a} \thinspace \text{mod m} $
$\text{(2) Symmetric Property:}\text{ If a} \equiv \text{b} \thinspace \text{mod m then} \thinspace \text{b} \equiv \text{a} \thinspace \text{c}\text{mod m} $
$\text{(3)Transitive Property:}\thinspace \text{If a} \equiv \text{b} \thinspace \text{and} \thinspace \text{b} \equiv \text{c} \thinspace \text{mod m} \thinspace \text{and} \thinspace \text{a} \equiv \text{c} \thinspace \text{mod m} $

$\text{Let m} \in \mathbb{N}, \thinspace \text{a} \in \mathbb{Z}. \thinspace \text{By the division algorithm,} \exists \thinspace \text{q,r} \in \mathbb{Z}$
$ \text{such that a=mq+r and} \thinspace 0 \leq \text{r} <\text{m}.\thinspace \text{Then a-r=mq or} \thinspace \text{a} \equiv \text{r} \thinspace \text{mod m} $
$\text{Now suppose that a,b}\in \mathbb{Z}, \text{m}\in \mathbb{N}. \thinspace\text{a and b leave the same remainder when divided by m}$

The remainders are the same when divided by m

Exactly one of 0,1,...,m-1. This list is called the least positive residues mod m.

No opposite numbers are usually not symmetric

$\text{a=b+mk for some k} \in \mathbb{Z} $

$\text{a}^\text{n} \equiv \text{b}^\text{n} \thinspace \text{mod m} $

$\text{(1) a+c} \equiv \text{b+d} \thinspace \text{mod m} $
$\text{(2) ac} \equiv \text{bd} \thinspace \text{mod m} $

$\text{A linear congruence has the form ax} \equiv \text{b} \thinspace \text{mod m}$
$\text{such that a,b} \in \mathbb{Z}, \text{m} \in \mathbb{N} $

$\text{It is congruent to} \thinspace \text{d}_0+\text{d}_1+...+\text{d}_\text{n} \thinspace \text{mod 9 and to } \thinspace \text{d}_0\text{d}_1+....+(-1)^\text{n} \text{d}_\text{n} \thinspace \text{mod 11} $

(a,m)|b

$\text{ax} \equiv \text{b} \thinspace \text{mod m has a solution} $

$\text{ax} \equiv \text{b mod m has one solution so} \thinspace \exists \text{j} \in \mathbb{Z} \thinspace \text{such that aj} \equiv \text{1 mod m. This j is called an inverse for a mod m}$

$\text{ax} \equiv \text{b mod m always has a solution if (a,m)=1}$

maximum of the powers to which it occurs to m and n

multiple of the least common multiple of m and n or LCM(m,n)

It's their product: mn because they have no common primes

$\text{Let} \thinspace \text{m}_1,\text{m}_2 \thinspace \text{be relatively prime natural numbers and let} \thinspace \text{a}_1, \text{a}_2 \in \mathbb{Z}.$
$\text{Then the system of congruences: }$
$\text{x}\equiv\text{a}_1 \thinspace \text{mod m}_1,\text{x} \equiv \thinspace \text{mod m}_2 \thinspace \text{has a solution and is unique mod m}_1\text{m}_2$

then x is a solution to the two congruences

$\begin{rcases} \text{x}\equiv \text{a}_1 \thinspace \text{mod m}_1 \\ \text{x} \equiv \text{a}_2 \thinspace \text{mod m}_2 \\ \end{rcases} \text{x} \equiv \text{b}_2\thinspace \text{mod m}_1\text{m}_2$
$\begin{rcases} \text{x}\equiv \text{a}_3 \thinspace \text{mod m}_3 \end{rcases}(\text{m}_3,\text{m}_1,\text{m}_2)=1 \thinspace \text{so x} \equiv \text{b}_3\text{mod m}_1\text{m}_2\text{m}_3$

$\text{In general , given m}_1\text{m}_2,...,\text{m}_\text{r} \in \mathbb{N} \thinspace \text{such that} $
$ \forall \text{i,j} \in \{1,2,...,\text{r}\}, (\text{m}_\text{i}, \text{m}_\text{j})=1$

$\text{ Then the system of congruences}\thinspace\text{x} \equiv \text{a}_1 \thinspace\text{mod m}, \text{x} \equiv \text{a}_2 \thinspace \text{mod m},... $
$\text{x} \equiv \text{a}_\text{r} \thinspace \text{mod m}_\text{r} \thinspace \text{has a solution and it is unique mod m}_1\text{m}_2,...,\text{m}_\text{r} $

$\text{(p-1)!}\equiv -1 \equiv \text{p-1 mod p}$

$\text{Then a} \equiv \text{1 mod p or a} \equiv \text{-1 mod p}$

$\text{a} \equiv 1 \thinspace \text{or} \thinspace \text{a} \equiv \text{p-1 mod p}$

1,p-1, and (p-3)/2 pairs of least non-negative residues that are inverses to each other

$\text{a} \equiv \text{b} \thinspace \text{mod m. Furthermore a} \equiv \text{a'(mod p)} \iff \text{a=1 or a=p-1}.$

$\{1,2,...,\text{p-1}\}$

$\text{ax} \equiv \text{b (mod p) } \thinspace \text{has a solution}$

$\text{Let p be an odd prime,} \text{a} \in \mathbb{Z} \thinspace \text{and suppose that p} \nmid \text{a}. \text{Then a}^\text{p-1} \equiv \text{1 mod p}$

$\text{Let p be an odd prime,} \text{a} \in \mathbb{Z}.$
$ \text{Then a}^\text{p} \equiv \text{a} \thinspace \text{mod p. However, if p|a, then a}\equiv \text{0 mod p}.$

there will always be one number left over in the sum of additive inverses

sum of the additive inverses equal zero

$\text{No, this statement is not true. It is possible to disprove this statement using a counterexample. }$
$\text{One possible example of a counterexample is the number 341.}$
$\text{(2,341)=1 and 2}^{341}\equiv \text{2 mod 341 but 341=11*31 so 341 is a composite number and not a prime number}$

$\text{Notice that as b varies in} \{0,1,...,\text{m-1}\} \thinspace \text{each ax} \equiv \text{b mod m has a solution. }$
$\text{Since there only m x-value. Each x-value must account for exactly one B-value}$

$\text{So in particular} \thinspace \text{x}_0 \thinspace \text{to be a solution, this would mean m|}\text{ax}_0-\text{b},$
$ \text{this is equivalent to saying}\thinspace\text{ax}_0-\text{b}=\text{mk for some k} \in \mathbb{Z} $
$\text{i.e. a'd}\text{x}_0-\text{b'd=m'dk for some k} \in \mathbb{Z}$
$ \text{which is equivalent to a'}\text{x}_0-\text{b'=m'k for some k} \in \mathbb{Z} \thinspace \text{i.e. a'}\text{x}_0 \equiv \text{b'mod m'}$
$\text{because x} \equiv \text{t mod m} \iff \text{m|(x-t) but since m'|m then m'|(x-t) in this case so x} \equiv \text{t mod m' is a solution,}$
$\text{as are x} \equiv \text{t+m' mod m, x} \equiv \text{t+2m'mod m},...,\text{x}\equiv\text{t+(d-1)m'mod m},\text{x} \equiv \text{t+dm'mod m} $
$\text{which gets us the solution x}\equiv \text{t mod m, which we already have}$

The general formula for the Chinese Remainder Theorem only works with relatively prime modulo.

$\text{a}_1\text{t+a}_2\text{u}$