Elementary Number Theory

Express $-210$ in the form $a-13b$, where $a$ and $b$ are positive integers with $0\leq a\leq 12$.

Find $\gcd(-112,-35)$.

Find $\mathrm{lcm}(-112,-35)$.

Suppose $m=42$ and $n=70$. Let $d=\gcd(m,n)$.

1. Find $d$.

2. Hence find $\mathrm{lcm}(m,n)$.

3. Find two integers $x$ and $y$ such that $mx+ny=d$.

Express 44100 as a product of primes.

Let $m=5$ and $n=3$.

1. State the value of $17\mod m$.

2. Find an $x$ where $0\leq x<m$ and $19\equiv x\pmod{m}$.

3. If $A=1234n+5$, what is $A\mod n$?

Explain why $-n\equiv n\pmod{2n}$.

Find the last two digits of $778899^{112233}$.

Find the multiplicative inverse of 123 modulo 5.

Find the positive integer $a$ such that $\gcd(a,50)=5$ and $\mathrm{lcm}(a,50)=150$.

Let $a$ and $b$ be positive integers. If $\mathrm{lcm}(a,b)=a^{2}$, express $b$ in terms of $a$.

Prove that $5^{2n+3}\equiv 5\pmod{8}$ for all non-negative integers $n$.

Show that $n^{2}\mid(1+n)^{n}-1$ for all positive integers $n$.

Prove that $7^{3^{n}}\equiv 1\pmod{9}$ for all positive integers $n$.

Find all even perfect squares that are not multiples of 4.

Find the last 3 digits of $57^{2023}$.

Let $n$ be an integer.

1. Prove that if $n$ is positive, then $6\mid 2n^{3}+3n^{2}+n$.

2. Prove that $12\mid n^{4}-n^{2}$.

Prove 1.31 by using Bézout’s lemma (1.15).