# Thread: find its moduluo 19

1. ## find its moduluo 19

17! . 3 ^16 = a (mod 19)

what is a

2. Hello,

Originally Posted by szpengchao
17! . 3 ^16 = a (mod 19)

what is a
I'd do it straightforward, because I don't know any property letting us simplify this...

17!=2.3.4....16.17

(mod 19)
17=-2
16=-3
15=-4
14=-5
.
.
.

--> $17! \equiv 2^2 3^2 4^2 5^2 6^2 7^2 8^2 9^2 \mod 19$

----> $\boxed{17! \equiv ({\color{blue}2}\cdot{\color{red}3}\cdot4\cdot5\cd ot{\color{red}6}\cdot7\cdot8\cdot{\color{blue}9})^ 2 \mod 19}$

3x6= -1 mod 19

2x9= -1 mod 19

----> $17! \equiv ({\color{red}4}\cdot{\color{red}5}\cdot{\color{blu e}7}\cdot{\color{blue}8})^2 \mod 19$

4x5=19+1= 1 mod 19

7x8=56=57-1=3x19-1= -1 mod 19

----> $17! \equiv (-1)^2 \mod 19$

$\boxed{17! \cdot 3^{16} \equiv 3^{16} \mod 19}$

Now, calculate a in $3^{16} \equiv a \mod 19$

3. ## i do this a simple way

by wilson theorem
18! = -1 mod 19
by euler fermat
3^18=1 mod 19

times them together

18! * 3^18= -1 mod 19

by know, we have
3^16*17! =a mod 19

times both sides by 9*18, we have 162 a = 18 mod 19
divides both sides by 18, 9a=1 mod 19
9 has inverse 17, we then solve this get
a= 17 mod 19

is it right?

4. Originally Posted by szpengchao
by wilson theorem
18! = -1 mod 19
by euler fermat
3^18=1 mod 19

times them together

18! * 3^18= -1 mod 19

by know, we have
3^16*17! =a mod 19

times both sides by 9*18, we have 162 a = 18 mod 19
divides both sides by 18, 9a=1 mod 19 << SiMoon says : yep, it's possible because 18 is prime with 19
9 has inverse 17, we then solve this get
a= 17 mod 19

is it right?
I find the same result with my (veeeeery long method) ^^

I didn't know about Wilson's theorem, thanks

5. ## another problem

i try to put it into my calculator. but it doesnt work...

i hav another problem about solving simutalneous congruences

if we hav two congruences:

x= 1 mod 2
x= 3 mod 4

how to solve that?
i mean the general case if (mod n) and (mod m) and (m,n)>1 ???

6. Originally Posted by szpengchao
i try to put it into my calculator. but it doesnt work...
My calculator gives this result too

i hav another problem about solving simutalneous congruences

if we hav two congruences:

x= 1 mod 2
x= 3 mod 4

how to solve that?
i mean the general case if (mod n) and (mod m) and (m,n)>1 ???
Well, here I know that if x=3 mod 4, then x=1 mod 2.
So the sets of x such that x= 3 mod 4 is included in the sets of x such that x= 1 mod 2.
Hence, the solutions are every x such that x=3 mod 4.

More generally, there is the CNT if m and n are coprime. When they're not, I'd do it according to the situation...

cheers mate!