Help with mod questions..

[trickslapper]

1. 3x=7(mod13)-------------------------->want x>0

2. 8x+3=5(mod9)


let a and n be relatively prime for both questions.

I have the answers to both:

1.x=11
2. x=7

can someone show me the technique to do these kinds of problems? I don't have to see both i'm assuming they both work the same way so if i could see the solution to either one i'd appreciate it.

thanks!

EDIT: figured it out the process isn't as easy as i was hoping it'd be. If it comes out to be negative just rewrite it as an equivalent congruent class.

 

[royhaas]

The first one is easy since you must have \(\displaystyle 3x = 7 + 13n\) for some positive integer \(\displaystyle n\). Take a look at the second one and see if your answer makes sense.

 

[galactus]

Let's try #2:

The solution x=7 you have posted is easy enough to check, \(\displaystyle (8\cdot 7+3)-5=54\), which is certainly a multiple of 9.

But, to find all such solutions:

\(\displaystyle 8x+3\equiv 5(mod \;\ 9)\)

Subtract 3 from both sides and get:

\(\displaystyle 8x\equiv 2(mod \;\ 9)\)

Now, look for a multiple of 8 that is congruent to 2(mod 9).

How about 56?.

\(\displaystyle 8x\equiv 2\equiv 56(mod \;\ 9)\)

Multiply by \(\displaystyle 8^{-1}\)**:

\(\displaystyle x\equiv 56\cdot 8^{-1}\equiv 7\cdot 8\cdot 8^{-1}\equiv 7(mod \;\ 9)\)

So, \(\displaystyle x\equiv 7(mod \;\ 9)\) describes all solutions to \(\displaystyle 8x+3\equiv 5(mod \;\ 9)\)

**: a modular inverse of an integer b(mod m) is an integer \(\displaystyle b^{-1}\) such that

\(\displaystyle b\cdot b^{-1}\equiv 1(mod \;\ m)\)

so we call \(\displaystyle b^{-1}\) an inverse.