COMP 2711 HW 4

1

a

If $n=0$, it is divisible by 2

If $n$ is even, i.e. $n=2k$, $n^2+n=4k^2+2k=2(2k^2+k)$, which is divisible by 2

If $n$ is odd, i.e. $n=2k+1$, $n^2+n=(2k+1{)}^2+(2k+1)=4k^2+4k+1+2k+1=4k^2+6k+2=2(2k^2+3k+1)$, which is divisible by 2

Therefore, for any natural number $n$, $2\mid n^2+n$

b

$$\begin{array}{rl}{n}^3-n& =n(n^2-1)\\ & =(n-1)n(n+1)\end{array}$$

Since $n-1$, $n$, and $n+1$ are 3 consecutive numbers, at least one of them is divisible by 3

Therefore, for any natural number$n$, $3\mid n^3-n$

c

Note that $p^2-1=(p-1)(p+1)$

From part a, we know $2\mid p^2+p$, so $2\mid p(p+1)$, since $p$ is prime and $p$ must be odd, $p+1$ must be even and $2\mid p+1$, so $2\mid (p-1)(p+1)$ and $2\mid p^2-1$

From part b, we know $3\mid (p-1)p(p+1)$, and since $p$ is a prime number and $3\nmid p$, hence $3\mid (p-1)(p+1)$, so $3\mid p^2-1$

Since $p$ is a prime number and must be odd, $p+1$ and $p-1$ must be even numbers, so $4\mid (p-1)(p+1)$ and $4\mid p^2-1$

Since $2\mid p^2-1$, $3\mid p^2-1$, and $4\mid p^2-1$, we can conclude that $24\mid p^2-1$

$\text{pagebreak}$

2

Since $\overline{EEFF}=1100\times \overline{E}+11\times \overline{F}=11\times (100\times \overline{E}+\overline{F})$, we can see that $11\mid \overline{EEFF}$

$\overline{AB}$ and $\overline{CD}$ do not contain the same digit and hence $11\nmid \overline{AB}$ and $11\nmid \overline{CD}$, so their product also does not divide by 11

Therefore, by contradiction, $\overline{AB}\times \overline{CD}\ne \overline{EEFF}$ and Arman did something wrong in the multiplication

3

1. Prove that a number is a perfect square implies that it has an odd number of positive divisors

Let $n$ be an arbitrary non-negative integer, by prime factorization we obtain

$$n=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}$$

The number of positive divisors of $n$ is

$$(a_1+1)(a_2+1)\dots (a_k+1)$$

Let $n^2$ be a perfect square

$$\begin{array}{rl}{n}^2& =n\cdot n\\ & =(p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k})\cdot (p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k})\\ & =p_1^{2a_1}{p}_2^{2a_2}\dots p_k^{2a_k}\end{array}$$

The number of positive divisors of $n^2$ is

$$(2a_1+1)(2a_2+1)\dots (2a_k+1)$$

Since $2a_i$ must be even for any positive integer $i$, $2a_i+1$ must be odd and the product of any number of odd numbers is also odd, hence the number of positive divisors of a perfect square number is odd

2. Prove that if a number has an odd number of positive divisors implies that it is a perfect square number (continue on next page)

$\text{pagebreak}$

Let $n$ be an arbitrary non-negative integer, by prime factorization we obtain

$$n=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}$$

If the number of positive divisors of $n$ is odd, $(a_1+1)(a_2+1)\dots (a_k+1)$ is odd, which means $a_1,a_2,\dots ,a_k$ must be even numbers and hence divisible by 2, that means $n$ can be expressed as the product of 2 non-negative integers

$$\begin{array}{rl}n& =p_1^{2a_1^{\prime }}{p}_2^{2a_2^{\prime }}\dots p_k^{2a_k^{\prime }}\\ & =(p_1^{a_1^{\prime }}{p}_2^{a_2^{\prime }}\dots p_k^{a_k^{\prime }})\cdot (p_1^{a_1^{\prime }}{p}_2^{a_2^{\prime }}\dots p_k^{a_k^{\prime }})\end{array}$$

Therefore, a number is a perfect square if and only if it has an odd number of positive divisors

$\text{pagebreak}$

4

a

$$2023=1024+512+256+128+64+32+4+2+1$$ $$\begin{array}{rl}& 3^1\mathrm{mod}7=3\\ & 3^2\mathrm{mod}7=2\\ & 3^4\mathrm{mod}7=2^2\mathrm{mod}7=4\\ & 3^8\mathrm{mod}7=4^2\mathrm{mod}7=2\\ & 3^{16}\mathrm{mod}7=2^2\mathrm{mod}7=4\\ & 3^{32}\mathrm{mod}7=4^2\mathrm{mod}7=2\\ & 3^{64}\mathrm{mod}7=2^2\mathrm{mod}7=4\\ & 3^{128}\mathrm{mod}7=4^2\mathrm{mod}7=2\\ & 3^{256}\mathrm{mod}7=2^2\mathrm{mod}7=4\\ & 3^{512}\mathrm{mod}7=4^2\mathrm{mod}7=2\\ & 3^{1024}\mathrm{mod}7=2^2\mathrm{mod}7=4\end{array}$$ $$\begin{array}{rl}{3}^{2023}\mathrm{mod}7& =3^{1024+512+256+128+64+32+4+2+1}\mathrm{mod}7\\ & =(4\cdot 2\cdot 4\cdot 2\cdot 4\cdot 2\cdot 4\cdot 2\cdot 3)\mathrm{mod}7\\ & =(8\mathrm{mod}7\cdot 4\cdot 2\cdot 4\cdot 2\cdot 4\cdot 2\cdot 3)\mathrm{mod}7\\ & =(1\cdot 4\cdot 2\cdot 4\cdot 2\cdot 4\cdot 2\cdot 3)\mathrm{mod}7\\ & =(1\cdot 4\cdot 2\cdot 4\cdot 2\cdot 3)\mathrm{mod}7\\ & =(1\cdot 4\cdot 2\cdot 3)\mathrm{mod}7\\ & =(1\cdot 3)\mathrm{mod}7\\ & =3\mathrm{mod}7\\ & =3\end{array}$$

b

$$\begin{array}{r}{3}^1=3\\ 3^2=9\\ 3^3=27\\ 3^4=81\\ 3^5=243\\ 3^6=729\\ 3^7=2187\\ 3^8=6561\\ 3^9=19683\\ ⋮\end{array}$$

We can observe that the unit digit of the power of 3 repeats in a cycle of 4 (3, 9, 7, 1), corresponding to the remainder of the power when divided by 4 (1, 2, 3, 0)

Since the power tower consist of 3, which is an odd number, the number of 3’s in the flattened form (3 to the power of some arbitrary number = 3 multiply by itself some arbitrary number of times) must be odd, because the product of any number of odd numbers is still odd

$$\begin{array}{rl}x\mathrm{mod}4& =3^{3^{3^{{.}^{{.}^{{.}^3}}}}}\mathrm{mod}4\\ & =(\underset{\text{odd number of times}}{\underbrace{3\times 3\times \cdots \times 3}})\mathrm{mod}4\\ & =((3\times 3)\mathrm{mod}4\times (3\times 3)\mathrm{mod}4\times \cdots \times 3)\mathrm{mod}4\\ & =(1\times 1\times \cdots \times 3)\mathrm{mod}4\\ & =3\mathrm{mod}4\\ & =3\end{array}$$

Therefore, the remainder 3 correspond to 7, so the unit digit of $3^x$ should be 7

$\text{pagebreak}$

5

a

$$304x\equiv 123(\mathrm{mod}571)$$ $$\gcd (571,304)=jx+ky$$ $$k=jq+r$$ $$\begin{array}{cccccc}k& j& r& q& x& y\\ 571& 304& 267& 1& -216& 115\\ 304& 267& 37& 1& 115& -101\\ 267& 37& 8& 7& -101& 14\\ 37& 8& 5& 4& 14& -3\\ 8& 5& 3& 1& -3& 2\\ 5& 3& 2& 1& 2& -1\\ 3& 2& 1& 1& -1& 1\\ 2& 1& 0& 2& 1& 0\end{array}$$ $$304^{-1}=-216\mathrm{mod}571=355$$ $$\begin{array}{rl}304x& \equiv 123(\mathrm{mod}571)\\ (304\cdot 355)x& \equiv 123\cdot 355(\mathrm{mod}571)\\ x& \equiv 269\end{array}$$

$\text{pagebreak}$

b

$$\begin{array}{rl}x& \equiv 3(\mathrm{mod}10)\\ x& \equiv 8(\mathrm{mod}15)\end{array}$$

By prime factorization

$$\begin{array}{rl}x& \equiv 3(\mathrm{mod}2)\\ x& \equiv 3(\mathrm{mod}5)\\ x& \equiv 8(\mathrm{mod}3)\\ x& \equiv 8(\mathrm{mod}5)\end{array}$$

Simplify

$$\begin{array}{rl}x& \equiv 3(\mathrm{mod}2)\\ x& \equiv 8(\mathrm{mod}3)\\ x& \equiv 3(\mathrm{mod}5)\end{array}$$

By Chinese Remainder Theorem

$$\begin{array}{rl}x& =\left(a_1\frac{m_1{m}_2{m}_3}{m_1}{y}_1+a_2\frac{m_1{m}_2{m}_3}{m_2}{y}_2+a_3\frac{m_1{m}_2{m}_3}{m_3}{y}_3\right)\mathrm{mod}30\\ & =\left(3\cdot \frac{2\cdot 3\cdot 5}{2}\cdot 1+8\cdot \frac{2\cdot 3\cdot 5}{3}\cdot 1+3\cdot \frac{2\cdot 3\cdot 5}{5}\cdot 1\right)\mathrm{mod}30\\ & =\left(3\cdot 15+8\cdot 10+3\cdot 6\right)\mathrm{mod}30\\ & =143\mathrm{mod}30\\ & =23\end{array}$$

Verify

$$\begin{array}{rl}& 23\mathrm{mod}10=3\\ & 23\mathrm{mod}15=8\end{array}$$

Therefore

$$x=23$$

6

Note that a number is divisible by 3 if the sum of its digits is divisible by 3
Note that a number is divisible by 9 if the sum of its digits is divisible by 9

An arbitrary number $N$ can be represented as the following where $a_i$ for any non-negative integer $i$ are the digits of the number

$$N=10^n{a}_n+10^{n-1}{a}_{n-1}+\cdots +10^1{a}_1+10^0{a}_0$$

For the divisibility of 3,

$$\begin{array}{rl}N& \equiv 1^n{a}_n+1^{n-1}{a}_{n-1}+\cdots +1^1{a}_1+1^0{a}_0(\mathrm{mod}3)\\ N& \equiv a_n+a_{n-1}+\cdots +a_1+a_0(\mathrm{mod}3)\end{array}$$

Therefore, $N$ is divisible by 3 if the sum of its digits is divisible by 3

For the divisibility of 9,

$$\begin{array}{rl}N& \equiv 1^n{a}_n+1^{n-1}{a}_{n-1}+\cdots +1^1{a}_1+1^0{a}_0(\mathrm{mod}9)\\ N& \equiv a_n+a_{n-1}+\cdots +a_1+a_0(\mathrm{mod}9)\end{array}$$

Therefore, $N$ is divisible by 9 if the sum of its digits is divisible by 9

$2023\times 0+2023\times 1+2023\times 2=6069$, which is divisible by 3 but not 9, i.e. the number formed is divisible by 3 but not 9

However, a perfect square number that is divisible by 3 should have at least 2 divisors of 3 (proved in Q3), hence divisible by 9

Therefore, by contradiction, we cannot have any perfect square number that is formed by using 2023 zeroes, 2023 ones, and 2023 twos