Упражнения для сестры, часть 6

Do not use a calculator for any of these problems. Don't Google them, either.

Do your best to solve them, but if you get stuck and can't find an answer to all parts of a problem, don't worry. We can talk about it together, and you can always come back and try to solve it again later.

Don't forget to revisit some of the problems on previous sets that you never finished! If you don't have time to work on all of them, no problem - just pick the ones that are most interesting to you.

Problem 1. By now, you should have a pretty good-looking list of "basic facts" about $\mathbb Z$. As before, give it another look and really think about whether each of its items is redundant. Also try to make sure it is detailed enough to distinguish $\mathbb Z$ from other number systems (e.g. $\mathbb Z_n$ for some small values of $n$, $\mathbb Z[i]$, $\mathbb Q$, $\mathbb R$, etc).

Now, try to prove this fact, which you are already familiar with: "for all $a,b\in\mathbb Z$, the equation $ax + by = 1$ has a solution if and only if $\gcd(a,b) = 1$".

This may be difficult, but make your best attempt. Take your time and be thorough. You will probably need to prove several intermediate "lemmas". You may want to keep your previous work well-organized so that you can refer back to it.

Here are some things you might need to do along the way:

• Prove some basic facts about divisibility (e.g. from the previous problem set)
• Define formally what the GCD is
• Prove that two integers always have a GCD (or do they?)
• Prove some basic facts about inequalities with $\leq$

You might be tempted to use some "advanced" things that you know about $\mathbb Z$, e.g. something or other to do with prime factorizations. But remember that anything you want to use, you will need to prove from your "basic facts". Don't make your job even harder by using a fact that is even more difficult to prove!

Problem 2. In $\mathbb Z$, we say that a number is a "square number" if it equals $y^2$ for some $y\in\mathbb Z$. For example, $0,1,4,9,16$ and $1002001$ are examples of square numbers.

Similarly, we might call a number in $\mathbb Z_m$ a "square number" if it is the square of another element of $\mathbb Z_m$. Calculate the following:

• What are all of the square numbers in $\mathbb Z_2$?
• What are all of the square numbers in $\mathbb Z_3$?
• What are all of the square numbers in $\mathbb Z_4$?
• What are all of the square numbers in $\mathbb Z_5$?
• What are all of the square numbers in $\mathbb Z_{29}$?
• What are all of the square numbers in $\mathbb Z_{31}$?

Can you use anything from previous problem sets (e.g. S3P1) to make your work easier? Do you notice any interesting patterns? Any conjectures? Is there anything you can say about how many square numbers $\mathbb Z_m$ has in general?

Problem 3. Consider this polynomial function: $$f(x) = x^3 + x^2 - 2x - 1$$ This polynomial has three different real roots $a,b,c\in\mathbb R$. They have the following approximate values: $$\begin{align*}a &\approx 1.247 \\ b &\approx -0.445 \\ c &\approx -1.802\end{align*}$$ However, strangely enough, the following expressions are all integers. Can you find the values of these integers?

$$\begin{align*}& a + b + c \\ & a\cdot b\cdot c \\ & a^2 + b^2 + c^2 \\ & a^3 + b^3 + c^3\end{align*}$$