1

Proof
(1):

So $gcd(7469,2464)=77$

So $gcd(4001,2464)=1$.

So $gcd(3997,2947)=7$.

So $gcd(4999,1109)=1$.
☐

2

Proof
For finding $gcd$:

So $gcd(1819,3587)=17$. Solving where $b=1819,c=3587$:

Therefore comparing the two:

☐

3

Proof
(1):
$gcd(423,198)=?$

So $gcd(423,198)=9$. Further:

So:

(2):

Thus $gcd(71,50)=1$. Further:

Therefore:

Here we have $\boxed{{\displaystyle x=-19,y=-27}}$.

(3):
$gcd(43,64)=?$:

So $gcd(43,64)=1$:

Therefore:

Here $\boxed{{\displaystyle x=3,y=-2}}$.

(4):
$gcd(93,81)=?$:

$gcd(93,81)=3$. But also:

Thus:

Here $\boxed{{\displaystyle x=7,y=8}}$.

(5):
Go one pair of $gcd$ terms at a time.

Thus $gcd(6,10)=2$ and:

Now:

Thus $gcd(6,10,15)=1$ but more importantly:

Thus:

Here $\boxed{{\displaystyle x=-14,y=7,b=1}}$.
☐

4

Proof
For each $\text{lcm}$ we can do the following:

(1):

So $gcd(482,1687)=241$ in fact if we notice further we have:

Therefore then:

(2):

They are 1 apart, so they can't share any common factors, so $gcd(60,61)=1$. Therefore:

☐

5

Proof
All we have to do is make an arithmetic progression by starting at the lowest number above 100 that's divisible by 7, and end before 1000 in a similar manner. Notice that:

Since $100=7\cdot 14+2$. Therefore, start at 102 in the AP:

Every 7 integers we move we get a new divisible by 7 number:

We want to know when:

Thus since $n$ is an integer:

Thus $n$ takes on $\boxed{{\displaystyle 129}}$ values, so clearly we have that many integers divisible by 7 in that range.

☐

6

Proof
To prove $6|n(n+1)(n+2)$ for all $n$, we have the following cases:

• If $n$ is even then clearly then $2|n$ so $2|n(n+1)(n+2)$.
• If $n$ is odd then clearly $n+1$ is even so then $n(n+1)(n+2)$ has a factor of 2.

Therefore clearly $2|n(n+1)(n+2)$. By a similar argument we have the following cases:

• If $n=3q+0$ then $3|n$ so then $3|n(n+1)(n+2)$
• If $n=3q+1$ then $n=3(q+1)-2$ by equivalence. Therefore then $n+2=3(q+1)$ so clearly $3|n+2$ by definition. So then $3|n(n+1)(n+2)$.
• If $n=3q+2$ then $n=3(q+1)-1$ by equivalence. Then $n+1=3(q+1)$ so clearly $3|n+1$ by definition. So then $3|n+1$ so $3|n(n+1)(n+2)$.
  In all cases we have $3|n(n+1)(n+2)$ so clearly $2\cdot 3=6$ divides $n(n+1)(n+2)$.

We can extend the fact that $24|n(n+1)(n+2)(n+3)$ by considering the cases:

• If $n=4q+0$ then $4|n$ so $4|n(n+1)(n+2)(n+3)$.
• If $n=4q+1$ then $n+3=4(q+1)$ so then $4|n+3$ so $4|n(n+1)(n+2)(n+3)$
• ... (continue with $n=4q+2$ and $n=4q+3$)
  We always get $4|n(n+1)(n+2)(n+3)$ so then since clearly $6|n(n+1)(n+2)(n+3)$ so then $6\cdot 4=24$ divides $n(n+1)(n+2)(n+3)$.

☐

7

Proof
We can't just choose 3 numbers that are all consecutive because of the second condition. What would help is to just take the prime numbers:

and take groups of factors for the different numbers. For example:

But this doesn't work since we need to have them be non-relatively prime in pairs. What would help is to instead choose shared factors; one between $a_1,a_2$, another between $a_2,a_3$, and another for $a_3,a_1$. For example:

Here we have $A=\{10,6,15\}$. All are relatively prime (not one prime factor exists between all of them); however, we do have it that $a_1,a_2$ share a factor of 2, and $a_2,a_3$ share a factor of $3$, and $a_1,a_3$ share the factor of $5$.
☐

9

Proof
Suppose $ac|bc$, so then $\mathrm{\exists }q\in \mathbb{Z}$ where $ac(q)=bc$. Notice then that:

Now if $c=0$ then that would be an undefined case since then $0|0$, so we have to assume $c\ne 0$. Therefore $aq-b=0\Rightarrow b=aq$, so then $a|b$ as expected.
☐

11

Proof
Proof by induction, since clearly the case for $n$ will apply the same for $-n$ since $n^2=(-n{)}^2$.

For $n=0$ notice that $4\nmid 0^2+2\iff 4\nmid 2$ as expected. Now suppose that $4\nmid (n^2+2)$ for all $n$. We'll prove the $n+1$ case, namely:

So notice that we must show that $4\nmid 2n+1$, but this is easy. Assume for contradiction that instead $4|2n+1$ so then $4k=2n+1$. But then $1=4k-2n=2(2k-n)$. But 1 doesn't have a factor of 2! Therefore this is a contradiction, so then $4\nmid 2n+1$.
☐

13

Proof
(1): Notice that $n^2-n=n(n-1)$. Now if $n$ is even then clearly $2|n(n-1)$ and if $n$ is odd then $n-1$ is even so $2|n-1$ so then $2|n(n-1)$.

(2): Notice that $2|n^2-n$ so then since $n^3-n=n(n^2-1)=n(n-1)(n+1)$ which is divisible by 6 via 1.2 Practice#6.

(3): Notice that:

So then clearly via (2) then we have $6|n^5-n$. We just need to then show that $5|n^5-n$. Notice:

• If we have either $n=5q+r$ where $r=0,1,4$ then we have divisibility by our factors $n,n-1,n+1$.
• If we have $n=5q+2$ then $n^2+1=(5q+2{)}^2+1=10q^2+20q+4+1=5(2q^2+4q+1)$ so clearly $5|n^2+1$.
• If we have $n=5q+3$ then $n^2+1=(5q+3{)}^2+1=10q^2+20q+9+1=5(2q^2+4q+2)$ so clearly $5|n^2+1$
  In all cases we have divisibility by 5, so therefore then $30|n^5-n$.
  ☐

15

Proof
Say $x,y$ are odd. Then $x=2n+1$ and $y=2m+1$ for $n,m\in \mathbb{Z}$. Then:

Notice that $n^2+m^2+n+m$ is an integer so then $x^2+y^2=4k+2$. By the division algorithm then $x^2+y^2$ divided by $4$ always gives $r=2$ so then clearly $4\nmid x^2+y^2$.

To show that $x^2+y^2$ is even, notice:

So then $2|x^2+y^2$.
☐

17

Proof
Notice that using Euclid's Algorithm:

So then it terminates where $1=gcd(n,n+1)$. Furthermore:

☐

19

Proof
Let $S=\{a_i:i\in \mathbb{N}\wedge \mathrm{\forall }i(gcd(a_i,a_{i+1})=1\}$ be arbitrary, where each $a_i\in \mathbb{Z}$. We'll show that for all $i,j$ that $gcd(a_i,a_j)=1$.

Consider the sequence of integers of $a_i,...,a_j$. Namely:

Now let's induct over the difference $j-i$. If $j-i=1$, then we have:

where $i+1=j$. By definition of the set $S$ then $gcd(a_i,a_{i+1})=1$ as required.

Now consider for some $n$ that if we have $j-i=n$ then $gcd(a_i,a_j)=1$ via the inductive hypothesis. We'll show that $gcd(a_i,a_{j+1})=1$ and then we are done. Notice that:

But via the inductive hypothesis then $gcd(a_i,a_j)=1$, so then:

Completing the induction.
☐

21

Proof
We'll show $(\to )$ first. Suppose $n=6k+5$. We'll show that it is of the form $3k^{\prime }-1$. Notice that:

Choose $k^{\prime }=2k+2$. Then clearly $n=3k^{\prime }-1$ as expected.

Now $(\nleftarrow )$ via the following counter-example. Namely, if we have $k^{\prime }=1$ then:

Now if we assume for contradiction that $2=6k+5$ is a valid form then:

Which is impossible. Thus $2\ne 6k+5$.
☐

23

Proof
Let $n\in \mathbb{Z}$ be arbitrary. Notice that $n^2=(-n{)}^2$ so we can restrict $n\in \mathbb{N}$ specifically.

Notice by the Division Algorithm that since $n^2$ is an integer, then $3k,3k+1,3k+2$ are the only possible forms. So, we only have to show that $3k+2$ is impossible.

Assume for contradiction that $3k+2$ was indeed possible. Furthermore, since $n$ is an integer we have the following cases:

• $n=3m$. Then $n^2=9m^2$ so then $n^2=9m^2=3k+2\iff 3(2m^2-k)=2$ which is a contradiction (2 doesn't have a factor of 3).
• $n=3m+1$. Then $n^2=9m^2+6m+1=3k+2\iff 3(3m^2-2m-k)=1$ which is a contradiction (1 doesn't have a factor of 3).
• $n=3m+2$. Then $n^2=9m^2+12m+4=3k+2\iff 3(-3m^2-4m+k)=2$ which is a contradiction (2 doesn't have a factor of 3).
  In all cases we get a contradiction, so clearly $3k+2$ must be impossible.
  ☐

25

Proof
Let $x\in \mathbb{Z}$ be arbitrary. Then choose $y=100-x$ to fit with our first equation. We'll show that $gcd(x,y)=5$. Using Property 4 of our $gcd$ equivalences:

Now we know that $100$ has 5 as a factor. Thus, we can just choose $x=5k$ where $k\in \mathbb{Z}$ is arbitrary. Then clearly:

Thus to be more specific, choose only $k$ such that $gcd(k,20)=1$; in other words, choose $k$ such that $k$ is coprime with $20$.

To ensure that there are infinitely many $k$ to do this, just have $k=3^m$ where $m$ is any integer. We notice that $5\nmid 3$ and via induction over $m$ we can see that if $5\nmid 3^m$ then $5\nmid 3^{m+1}$ by Properties of Divisibility.
☐

27

Proof
Notice that:

So here:

Let $a\in \mathbb{Z}$ be arbitrary. Then clearly $b$ must just be all the factors that $a$ misses; namely it must be all the divisors of $1000$. We can go through them all:

Thus then the solutions are all $(a,b)$ such that $a$ is the missing divisor $d$ from the set from whatever $b$ is. In this case:

29

Proof
Always $\mathrm{\exists }g,l$ where $g=gcd(x,y)$ and $l=\text{lcm}(x,y)$ for any $x,y$. Now notice that if we have that then:

To show $(\leftarrow )$ suppose that $g|l$. Then $l=gk$ where $k\in {\mathbb{Z}}^{+}$ (has to be positive in these cases). Then:

Thus then just choose $x=g$ and $y=gk$ to complete the equation.

To show $(\to )$, suppose $\mathrm{\exists }x,y$ where $|xy|=gl$. We'll show that $g|l$. Namely, notice that since $g=gcd(x,y)$ then $x=g{k}_x$ and $y=g{k}_y$ by having $g$ as a divisor, for some $k_x,k_y\in {\mathbb{Z}}^{+}$. Then:

But since $g>0$ then $g\ne 0$ so then clearly:

Thus by definition since $k_x{k}_y$ is an integer, then $g|l$ as required.
☐

31

Proof
Let's prove this by induction over $k$. For the base case when $k=2$ notice that:

So since $n+1$ is an integer then clearly $(n-1)|n^2-1$ for the $k=2$ case.

Now suppose for induction that $(n-1)|(n^k-1)$ for the $k$-th case. We show that the $k+1$-th case is satisfied. Notice that:

Now notice that $(n-1)|n^k(n-1)$. Further by our inductive hypothesis then we have $(n-1)|(n^k-1)$. Therefore by Property 3 we have:

completing the inductive step.
☐

33 (Finish, look at gcd(a,b+ax) proof)

Proof
We'll prove the latter which proves the former. Let $x,y\in \mathbb{Z}$ be arbitrary:

Then if $d=gcd(a,b)=g$:

☐

35

Proof
We have two cases:

• If $a$ is even then $a=2k$ so $gcd(2k,2k+2)=2gcd(k,k+1)=2\cdot 1$ where we used 1.2 Practice#17.
• If $a$ is odd then $a=2k+1$ so:

But we already know $a$ is odd, so it doesn't have a factor of 2. Thus then $gcd(a,a+2)=1$ in this case.
☐

37 (try to do before 33)

Proof
Let's first prove that $gcd(a,b,c)=gcd(gcd(a,b),c)$, as once we have that then an induction on $n$ will finish the proof.

Consider $g=gcd(a,b,c)$. Then: $\mathrm{\exists }{x}_0,y_0,z_0$ where:

☐