solution verification modular arithmetic

Question

I am looking for solution verification. I am trying to grasp the very very basic idea of modular arithmetic. I am sure there are lot of other ways to go about it assuming I did these problems correctly.

$3k \equiv 7 \pmod{13}$ since we are in $\mod(13)$ we only look at the values $k=0,...,12$

so $$3k -7 \equiv 0 \pmod{13}$$

$(k = 1) \space 3 - 7 =-4$

$(k = 2) \space 6 - 7 = -1$

$(k = 3) \space 9 - 7 = 2$

$(k = 4) \space 12 - 7 = 5$

$(k = 5) \space 15 - 7 = 8$

$(k = 6) \space 18 - 7 = 11$

$(k = 7) \space 21 - 7 = 14$

$(k = 8) \space 24 - 7 = 17$

$(k = 9) \space 27 - 7 = 20$

$(k = 10) \space 30 - 7 = 23$

$(k = 11) \space 33 - 7 = 26$

Now listing multiples of $13$:

13

26

39

we get $26$ when $k = 11$ so the answer is $11$

$4k \equiv 2 (\mod 7)$

$4k - 2 \equiv \space 0 (\mod 7)$

we look at the values from $0,1,2....6$

$(k = 1) 4 - 2 = 2$

$(k = 2) 8 - 2 =6$

$(k = 3) 12 - 2 = 10$

$(k = 4) 16 - 2 = 14$

$(k = 5) 20 - 2 =18$

$(k = 6) 24 - 2 = 22$

listing multiples of $7: 7, 14 , 21 , 28$

we get $14$ when when $k = 4$ so the solution to the congruence equation is $k = 4$

Answer 1

Hint:

Find a Bézout's relation $3u+13 v=1$ to determine the inverse $u$ of $3$ modulo $13$, so that you have $$3k\equiv 7\mod 13\iff k\equiv u\cdot 7\mod 13. $$

Answer 2

For small numbers, a practical method is as follows.

$4k\equiv 2\mod 7$

Run through the addition of $2$ to successive multiples of $7$. $$2,9,16,...$$ until you get a multiple of $4$.

The solution is $k=4.$

$3k\equiv 7\mod 13$

$7,20,33,...$

The solution is $k=11.$

Answer 3

$$3k=13n+7\iff 3(k-2n)=7(n+1)$$

So you can take $n+1=3$ and $k-2n=7$, or $k=11$.

Answer 4

The basic idea behind modular arithmetic is to express quantities in the form of linear polynomials with integer slopes ( okay one way to state the basic idea). So we have:

$y\equiv b\pmod m\iff y=mx+b$

This gives us the power to reduce higher numbers (like 78 digits +) down to easily workable sizes. It also allows reducing input size in higher degree polynomials, find solutions, including integer roots, as they need to be roots modulo every integer. Even assessing what solutions will look like to diophantine equations.

Your solutions are correct, but it's the tedious way to go. Once k is greater than 7 you could start using mod 7 to skip some.

Another way is to use the definition to get $3k=13x+7=(3\cdot 4+1)x+(3\cdot 2+1)$ which means $z\equiv 2\pmod 3$ by distributivity and additive inverse. Then we check $13\cdot 2+7=33=3\cdot 11$ making $k=11$ a solution.

There are obviously other methods, like modular multiplicative inverse ( to do the equivalent of division), etc. but they're more useful for when you can't calculate a minimum $x$ value quickly.

Answer 5

Your reasoning is correct but you are making it way too hard.

Its easier to and or subtract thirteen to get into range immediately.

$(k=1) 3-7=-4\implies -4+13=9$.

$(k=2) 6-7=-1\implies -1 + 13=12$.

$(k=3) 9-7 = 2$

$(k=4) 12-7=5$

$(k=5) 15-7=8$.

$(k=6) 18-7=11$

$(k=7) 21-7=14\implies 14-13=1$.

$(k=8) 24-7=17\implies 17-13=4$

$(k=9) 27-7=20\implies 20-13=7$.

$(k=10) 30-7=23\implies 23-13=10$

$(k=11) 33-7=26 \implies 26-13=13\implies 13-13 = 0$ !STOP!

.... It's even easier to just realize that each step is $3$ more than the last and circle AS you go around.

To get $3k \equiv 7\pmod {13}$ just add $3$ until you reach $7$....

$3, 6,9,12,15\equiv 2,5,8,11,14\equiv 1, 4, \color{blue}7$.

And that is ...one, two, three, .... , $11$ terms in.

Of course we are making it way too hard on ourselves.

$3$ and $13$ are relatively prime so one of $7, 7+13,$ or $7+26$ will be divisible by $3$. $7$ isn't, and $7+13=20$ isn't but $7+26 = 33 = 3*11$ is.

So $3*11 \equiv 7 \pmod {13}$ is a solution.

....

Of course that could be hard if we were aske to solve $17k \equiv 56\pmod {89}$.

It be too much work to list $56, 56+89, 56+2*89,....., 56+16*89$ and seeing which one is divisible by $17$ (although that will work in theory)

Instead we can figure that $89 = 5*17+4$ so $1*89 - 5*17 = 4$..

And $17 = 4*4 + 1$ so $1 = 1*17 - 4*4$ so

$1 = 1*17 - 4*(1*89 - 5*17) = 1*17 +20*17 -4*89 = 21*17 -4*89$

so $17*21 = 1 + 4*89$ so

$17*21 \equiv 1 \pmod{89}$

sp $17*(21\times 56) \equiv 56\pmod{89}$

Now $21*56= 84*14 =(89-5)*14 = -70 + 14*89 =19 + 15*89$

so $17*(21\times 56) = 17*(19 + 15*89) = 17*19 + 17*15*89\equiv 56\pmod{89}$ and the solution is $17*19\equiv 56 \pmod {89}$.