Congruence of variable x, y and z

Question

i have this particular question regarding congruence consisting of x,y and z variables. the question is as such: Let x and y be integers such that x≡5(mod 8) and y≡3(mod 8). Find the integer z such that 0 ≤ z ≤7 and 68x+2y^2≡z(mod 8).

since both equations has the modulo of 8, my first attempt was to perform addition of congruences with the x and y:

x+y≡ 8(mod8)

because I'm new to this, I'm not sure how would i proceed on on obtaining the integer z. any tips? I'm pretty sure the Euclidean Algorithm would lead me to find the integer of z in the later stage but I'm confused on the additional equation of 68x+2y^2≡z(mod 8)

Answer 1

You just need to do some calculation $\bmod 8$. It is a lot simpler than you are trying to make it.

$68x+2y^2 \equiv 340+ 18 \equiv 4 + 2 \equiv 6 \bmod 8$

Note that I could have reduced the $68$ before multiplying it in to the $x$, and also could have summed the components before reducing to a remainder over a multiple of $8$:

$68x+2y^2 \equiv 4x+2y^2 \equiv 20+ 18 \equiv 38 \equiv 6 \bmod 8$

Answer 2

We can work with arithmetic modulo 8.

Remember the following general statements:

If $a\equiv A\pmod{n}$ and $b\equiv B\pmod{n}$ then

• $a+b\equiv A+B\pmod{n}$

• $ab\equiv AB\pmod{n}$

• $a^k\equiv A^k\pmod{n}$

---

In other words, we may simply replace any occurrence of a number with what it is equivalent to (so long as it was one of the numbers being added or multiplied or base of an exponent., numbers in the exponent itself can't be replaced as easily)

So, since we have $x\equiv 5\pmod{8}$ and $y\equiv 3\pmod{8}$ this implies

$68x+2y^2\equiv 68\cdot 5 + 2\cdot 3^2\equiv 4\cdot 5+2\cdot 9\equiv \dots \pmod{8}$

Continue making small simplifications when and where you can until you eventually arrive at an answer in the desired range.