17! . 3 ^16 = a (mod 19)
what is a
Hello,
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
.
.
.
--> $\displaystyle 17! \equiv 2^2 3^2 4^2 5^2 6^2 7^2 8^2 9^2 \mod 19$
----> $\displaystyle \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
----> $\displaystyle 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
----> $\displaystyle 17! \equiv (-1)^2 \mod 19$
$\displaystyle \boxed{17! \cdot 3^{16} \equiv 3^{16} \mod 19}$
Now, calculate a in $\displaystyle 3^{16} \equiv a \mod 19$
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?
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 ???
My calculator gives this result too
Well, here I know that if x=3 mod 4, then x=1 mod 2.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 ???
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...