# Congruency proofs

so I dont know if this is really what the website is meant for so let me know. I have a midterm on abstract algebra (intro) and I've been doing practice problems and I just need to know whether my answers are correct and if my way of doing them is right.

1) Does the following have a solution: $x^2 \equiv 1 \pmod{3}$ Well we know that a solution exists if $\mathrm{gcd}(a, n) | b$ where $a = x^2$, $b = 1$ and $n = 3$. we can rewrite the equation as $1 \equiv x^2 \pmod{3}$

2) If $a \equiv 3 \pmod{4}$ prove that there are no integers c, d such that $a = c^2 + d^2$ By definition we can write this as $a = 4n + 3, n \in \mathbb{Z}$. so does this prove it? since $4n + 3$ can never be in the form of $c^2 + d^2$.

3) Show that no perfect square has 2, 3, 7, 8 as its last digit. The way we did this was we listed out all the classes from in $\mathbb{Z}_{10}$ which are $[0]_{10}..[9]_{10}$ and showed that $a^2 (0, 1, 4, 16, 25 ...)$ are never an element of the $[2], [3], [7], [8]$

4) If $a \in \mathbb{Z}$, prove that last digit of $a^4$ is $0, 1, 5, \text{or } 6$

-
As I mentioned before, the way to write $\mathbb{Z}$ (the integers) is to write \textbb{Z}, not $ZZ$. – Arturo Magidin Nov 16 '10 at 3:54
Hey sorry. thanks for correcting. – Tyler Hilton Nov 16 '10 at 5:00

For (1), you confused the condition for a congruence of the form $ax\equiv b\pmod{n}$ to have a solution with the congruence you have here. This congruence is not a linear congruence, so the condition does not apply.

No, that does not even begin to work; it's completely different kinds of congruences (linear vs. quadratic). And you did not determine if it had solutions or not, you just said that solving $x^2\equiv 1 \pmod{3}$ is the same as solving $1\equiv x^2\pmod{3}$. If I asked you to figure out if there is an integer such that $x^2=4$, would saying "that's the same as finding an integer such that $4=x^2$" constitute a valid answer that solves the problem of determining if there is or is not such an integer? No.

The simplest way to solve this one is to check: there are only three possible values for $x$ modulo $3$, namely $0$, $1$, or $2$. Do any of them give you a solution to the congruence?

More generally, you can use the ideas hinted at in Bill Dubuque's answer.

For (2), you aren't proving anything; you are just repeating what you have been asked to prove. Proving it requires more than just repeating the statement with conviction. Why is it that $4k+3$ can never be written in the form $a^2+b^2$? You never say, you just assert it.

Instead, think about what $a^2+b^2$ would be modulo $4$. What are the possible values of $a^2$ modulo $4$? Of $b^2$? So what are the possible values of $a^2+b^2$ modulo $4$?

(3) is essentially correct.

For (4), try the same approach as (3).

-

1) prime $\rm\: p\:|\:(x-1)(x+1)\ \Rightarrow\ p|(x-1)\ \ or\ \ p|(x+1)$

2) $\rm\ even^2\equiv 0,\ odd^2\equiv 1\ (mod\ 4)\$ so two squares can't have sum $\equiv 3$

4) By 3) $\rm\ a^2\not\equiv \{\pm2,\:\pm3\}\ \Rightarrow\ a^2 \equiv \{0,\:\pm1,\:\pm4,\:5\}\ \Rightarrow\ a^4\equiv \{0,1,6,5\}\ \:(mod\ 10)$

-

For 1) you have just rewritten the equation backwards, so have not proved anything. You can use the same approach as 3)-square each number mod 3 and see if any square to 1

For 2) why do you know 4n+3 cannot be the sum of two squares? You need to list the numbers mod 4 that are squares, then find that no pair of them sums to 3

For 4) do it just like 3, but using the fourth power.

-
I dont get how to do number 2. What do you mean list numbers mod 4? – Tyler Hilton Nov 16 '10 at 0:00
Take all the numbers mod 4, which are 0,1,2,3 and square them mod 4. – Ross Millikan Nov 16 '10 at 0:01