Answer to Question #135648 in Combinatorics | Number Theory for Aji

Question

Using Wilson's and Fermat's Little Theorem
What is the remainder when:
1.) 3^{31}\div73 31 ÷ 7
2.) 5^{119}\div595 119 ÷ 59
3.) 2^{70}+3^{30}\div132 70 + 3 30 ÷ 13
4.) 53!\div6153 ! ÷ 61
5.) 149!\div139149 ! ÷ 139
Find all integers x such that: x^{86}\equiv6\left(\mod29\right)

Answer 1

1) By Fermat’s Little Theorem,

$3^{7-1}\equiv1(\bmod7)$

Then

$3^{12}\equiv1(\bmod7),$ $3^{18}\equiv1(\bmod7),$ $3^{24}\equiv1(\bmod7),$ $3^{30}\equiv1(\bmod7)$

$3^{1}\equiv3(\bmod7)$

$3^{31}\equiv3(\bmod7)$

2) By Fermat’s Little Theorem,

$5^{59-1}\equiv1(\bmod59)$

Then $5^{116}\equiv1(\bmod59),$

$5^{3}\equiv7(\bmod59)$

$5^{119}\equiv7(\bmod59)$

3) By Fermat’s Little Theorem,

$2^{13-1}\equiv1(\bmod13), 3^{13-1}\equiv1(\bmod13)$

$2^{60}\equiv1(\bmod13), 3^{24}\equiv1(\bmod13)$

Then

$2^{70}+3^{30}\equiv2^{10}+3^{6}\equiv1024+729\equiv$

$\equiv114+79\equiv193\equiv11(\bmod13)$

$2^{70}+3^{30}\equiv11(\bmod13)$

4) By Wilson's Theorem,

$(61-1)!\equiv-1(\bmod61)$

$(-1)(-2)(-3)(-4)(-5)(-6)(-7)53!\equiv-1(\bmod61)$

$53!(2)(3)(4)(5)(6)(7)\equiv1(\bmod61)$

$(2)(5)(6)=60$

$53!(-1)(3)(4)(7)\equiv1(\bmod61)$

$53!(3)(4)(7)\equiv-1(\bmod61)$

$(3)(4)(7)=84$

$53!(23)\equiv-1(\bmod61)$

Let's do Euclidean algorithm to compute $23^{-1}$ $\bmod61$

$61=2(23)+15$

$23=15+8$

$15=8+7$

$8=7+1$

Hence

$1=8-7=8-(15-8)=2(8)-15=2(23-15)-15=$

$=2(23)-3(15)=2(23)-3(61-2(23))=$

$=8(23)-3(61)$

$23^{-1}\equiv8(\bmod61)$

Hence

$53!\equiv-8(\bmod61)$

$53!\equiv53(\bmod61)$

5) 139 is the  prime number. By Wilson's Theorem,

$(139-1)!\equiv-1(\bmod139)$

$(10)(9)(8)(7)(6)(5)(4)(3)(2)(1)(-1)\equiv$

$\equiv(9)(8)(6)(5)(4)(3)(-1)\equiv(9)(8)(3)(-19)(-1)\equiv$

$\equiv(27)(13)\equiv73(\bmod139)$

$149!\equiv73(\bmod139)$

6) By Fermat’s Little Theorem,

$x^{29-1}\equiv1(\bmod29)$

$86=3(28)+2$

$x^{86}\equiv x^2(\bmod29)$

Then

$x^{2}\equiv 6(\bmod29)$

$x^{2}\equiv 64(\bmod29)$

$x^{2}-64\equiv 0(\bmod29)$

$(x-8)(x+8)\equiv (\bmod29)$

$x\equiv 8(\bmod29)$ or $x\equiv 21(\bmod29)$