+0

# Modular Number Theory

0
197
6
+46

Hi, I hace been stuck for a while on this. 11 is not the answer.

If a,b,c are positive integers less than 13 such that

\begin{align*} 2ab+bc+ca&\equiv 0\pmod{13}\\ ab+2bc+ca&\equiv 6abc\pmod{13}\\ ab+bc+2ca&\equiv 8abc\pmod {13} \end{align*}

then determine the remainder a+b+c is divided by 13.

May 2, 2022

#1
+9461
+8

Since 13 is a prime, every integer has its inverse mod 13.

We can rewrite this system as

$$\begin{cases} 2a^{-1} + b^{-1} + c^{-1} \equiv 6 \pmod{13}\\ a^{-1} + 2b^{-1} + c^{-1} \equiv 8\pmod{13}\\ a^{-1} + b^{-1} + 2c^{-1} \equiv0 \pmod{13}\\ \end{cases}$$

Simplifying gives

$$\begin{cases} a^{-1} + 2b^{-1} + c^{-1} \equiv 8 \pmod{13}\\ -b^{-1} + c^{-1} \equiv 5\pmod{13}\\ -4b^{-1} \equiv8 \pmod{13}\\ \end{cases}$$

Then $$b^{-1} \equiv 11\pmod{13}$$$$c^{-1} \equiv 3 \pmod{13}$$, and $$a^{-1} \equiv 9\pmod{13}$$.

Inverting each of them gives $$a \equiv 3\pmod{13}$$$$b\equiv 6\pmod{13}$$, and $$c\equiv9\pmod{13}$$.

Then $$a + b + c \equiv 5\pmod{13}$$. The remainder is 5.

May 2, 2022
#2
+46
+1

Thank you so much, that is correct.

SpaceXGeek  May 2, 2022
#3
+118229
0

Max wants to know that you learned something.

Not that you copied his final answer into a box and it came up magically with "correct"

Your 'that is correct' is insulting and suggest do me that you are just copying the final answer with no understanding at all.

Melody  May 2, 2022
#4
+148
+3

Excellent use of results from Number Theory and Algebra, Max!!!

Anthrax  May 3, 2022
#6
+9461
+2

Anthrax: thank you!

SpaceXGeek:

As Melody mentioned, the main point of this solution is for you to learn something.

If I give you a similar problem, would you be able to solve it?

Here's a similar problem to check your understanding:

Suppose we have positive integers a, b, c such that $$\begin{cases}3ab + bc + ca \equiv 9abc\pmod{11}\\ab + 3bc + ca \equiv abc\pmod{11}\\ab + bc + 3ca \equiv 10abc \pmod{11}\end{cases}$$, then can you find the remainder when a + b + c is divided by 11?

Remarks and some hints: When you only have ab, bc, ca and abc in an equation (or congruence, in this case), it is sometimes useful to consider 1/a, 1/b, 1/c. Here, I had to make sure that 1/a, 1/b, and 1/c "makes sense" under mod 13, so I pointed out that 13 is a prime. The simplification step is actually Gaussian elimination, if you have learnt linear algebra. Otherwise, you can use method of elimination to solve it. You can invert an integer a mod p by calculating $$a^{-1} \equiv a^{p - 2}\pmod p$$. This congruence comes from Fermat's little theorem.

MaxWong  May 3, 2022
edited by MaxWong  May 3, 2022
edited by MaxWong  May 3, 2022
edited by MaxWong  May 3, 2022
#5
+118229
+1

Thanks Max,

I just spent time working through your solution by hand. I needed the practice.

I never would of got that first step without your guidence :)

May 3, 2022