Number Theory Problem Set (Modular Arithmetic)

1. Let  $a \equiv 1 \pmod{4}$

Find the value of 6a + 5 (mod 4). Express your answer as a residue between 0 and the modulus.

6a + 5 (mod 4)

=(6*1 + 5) (mod 4)

=11(mod4)            

            11/4=2R3      or      3R-1

= 3 or -1  (mod4)

4. Given

$a \equiv 1 \pmod{7}$,

$b \equiv 2 \pmod{7}$,

and

$c \equiv 6 \pmod{7}$,

what is the remainder when

$a^{81} b^{91} c^{27}$

is divided by 7?

$\begin{array}{|rclcl|} \hline a-1 &=& 7l \quad &\text{or}& \quad a =7l+1 \\ b-2 &=& 7m \quad &\text{or}& \quad b =7m+2 \\ c-6 &=& 7n \quad &\text{or}& \quad c =7n+6 \\ \hline \end{array}$

$\begin{array}{|rclcl|} \hline && a^{81} b^{91} c^{27} \pmod 7 \\ &\equiv& (7l+1)^{81}\cdot (7m+2)^{91}\cdot (7n+6)^{27} \pmod 7 \\\\ &\equiv& \left[\binom{81}{0}(7l)^{81}+ \binom{81}{1}(7l)^{80} +\dots + \binom{81}{81} 1^{81} \right] \\ && \cdot \left[\binom{91}{0}(7m)^{91}+ \binom{91}{1}(7m)^{90} +\dots + \binom{91}{91} 2^{91} \right] \\ && \cdot \left[\binom{27}{0}(7n)^{27}+ \binom{27}{1}(7n)^{26} +\dots + \binom{27}{27} 6^{27} \right] \pmod 7 \\\\ &\equiv& \binom{81}{81} 1^{81}\cdot \binom{91}{91} 2^{91} \cdot \binom{27}{27} 6^{27}\pmod 7 \\\\ &\equiv& 1^{81}\cdot 2^{91} \cdot 6^{27}\pmod 7 \\ &\equiv& 1 \cdot 2^{91} \cdot 6^{27}\pmod 7 \\ &\equiv& 2^{91} \cdot 6^{27}\pmod 7 \\ \hline \end{array}$

$\begin{array}{|lllcl|} \hline \text{Because } gcd(2,7) = 1 \quad \Rightarrow & 2^{\varphi(7)} \equiv 1 \pmod 7 \qquad \varphi(7) = 6\\ & \mathbf{2^{6} \equiv 1 \pmod 7} \\\\ \text{Because } gcd(6,7) = 1 \quad \Rightarrow & 6^{\varphi(7)} \equiv 1 \pmod 7 \qquad \varphi(7) = 6\\ & \mathbf{6^{6} \equiv 1 \pmod 7} \\ \hline \end{array}$

$\begin{array}{|rclcl|} \hline && a^{81} b^{91} c^{27} \pmod 7 \\ &\equiv& 2^{91} \cdot 6^{27}\pmod 7 \\ &\equiv& 2^{6\cdot 15+1} \cdot 6^{6\cdot 4+3}\pmod 7 \\ &\equiv& 2^{6\cdot 15}\cdot 2 \cdot 6^{6\cdot 4}\cdot 6^3 \pmod 7 \\ &\equiv& (2^6)^{15}\cdot 2 \cdot (6^6)^{4}\cdot 6^3\pmod 7 \qquad \mathbf{2^{6} \equiv 1 \pmod 7}\\ &\equiv& (1)^{15}\cdot 2 \cdot (6^6)^{4}\cdot 6^3\pmod 7 \qquad \mathbf{6^{6} \equiv 1 \pmod 7}\\ &\equiv& (1)^{15}\cdot 2 \cdot (1)^{4}\cdot 6^3\pmod 7 \\ &\equiv& 1 \cdot 2 \cdot 1 \cdot 6^3\pmod 7 \\ &\equiv& 2 \cdot 6^3 \pmod 7 \\ &\equiv& 2 \cdot 216 \pmod 7 \\ &\equiv& 432 \pmod 7 \\ &\equiv& \mathbf{5} \pmod 7 \\ \hline \end{array}$

The remainder is 5

4) \;\;Given\;\; a \equiv 1 \pmod{7},\;\;and\;\; b \equiv 2 \pmod{7} \'\'and\;\; c \equiv 6 \pmod{7} \mbox { what is the remainder when }  a^{81} b^{91} c^{27}   \mbox{is divided by 7}\?

$4) \;\;Given\;a \equiv 1 \pmod{7},\;\;and\; b \equiv 2 \pmod{7} \:and\;\; c \equiv 6 \pmod{7}\\ \mbox { what is the remainder when }  a^{81} b^{91} c^{27}\;  \mbox{is divided by 7}?$

Thanks   Heureka,

I have just finsihed Q4 too and I think our answers are fairly similar but I would like to post mine anyway :)

a=7p+1

b=7q+2

c=7r+6

p,q,r are integers

$a^{81}=(7p+1)^{81}=1^{81}+81*(7p)^1+81C2*(7p)^2.........+(7p)^{81}$

The only term here that is NOT a multiple of 7 is 1   and 1mod7=1

Using the same logic

$(7q+2)^{91}(mod 7) \\ =2^{91}(mod7)\\ =2^{10*9+1}(mod7) \\ =(2^{10})^{9}*2(mod7) \\ =(1024)^{9}*2(mod7) \\ =(2)^{9}*2(mod7) \\ =1*2(mod7) \\ =2(mod7)$

and

$(7r+6)^{27}(mod7)\\ =6^{27}(mod7)\\ =((6^3)^3)^3(mod7)\\ =(216^3)^3(mod7)\\ =(6)^3(mod7)\\ =6(mod7)$

so

$a^{81} b^{91} c^{27} (mod7)\\ =1*2*6(mod7)\\ =12(mod(7)\\ =5 (mod7)$

The remainder will be 5     Just like Heureka aready told us :)

$\huge{2)}$

$a^2\equiv 16 \pmod {10}\\a^2\equiv 6 \pmod {10}\\ a^2=\overline{X6}\;\;\mbox{<- This notation means 10X + 6 where }1\leq X\leq 9\\ \mbox{In 1 - 10 there are only 2 numbers whose squares end with 6, namely 4 and 6}\\ \therefore a=6$

$a^2\equiv 0 \pmod{12}\\ \text{That means }\dfrac{a^2}{12}\mbox{ is a positive integer or 0}\\ \mbox{However }a\neq 0 \mbox{ so }\dfrac{a^2}{12} \mbox{ can't be 0.}\\ \begin{array}{rcl}\\&&a^2=12x\end{array}\\ \text{Check the multiples of 12 from 12 to 144}\\ \text{12 is not a square number}\\\text{24 is not a square number}\\\color{red}\text{36 is a square number} \\\text{48 is not a square number}\\ $

$\text{60 is not a square number}\\\text{72 is not a square number}\\\text{84 is not a square number}\\\text{96 is not a square number} \\\text{108 is not a square number}\\\text{120 is not a square number}\\\text{132 is not a square number}\\ \text{144 is not a square number}$

$\begin{array}{rllll}&a^2&=&36&\\&a&=&\pm 6&\\&\text{a must not be -6}\\\therefore&a=6.\end{array}$

4) 1^81.2^91.6^27 =2.5340394e+48 mod 7 =5