Mathematics

  Example : Show that the integer $111^{333} + 333^{111}$ is divisible by $7$. Answer: Firstly, we will find the remainder when $111^{333} $ and $ 333^{111}$ is divided by $7$. Then with help of property $4.$ of Theorem , we show that  the integer $111^{333} + 333^{111}$ is divisible by $39$. We have $111 \equiv 6 ~(mod ~7)$ but $6 \equiv -1 ~(mod ~7) $. Therefore $111 \equiv -1 ~(mod ~7) $. By property $6.$ of Theorem , we have  $111^{2} \equiv 1 ~(mod ~7)$. We can write $333$ as $333 = 166 \cdot 2 + 1$. Therefore $111^{333} \equiv (111^{2})^{166} \cdot 111 \equiv 1^{166} \cdot 111 \equiv  6 ~(mod ~7)$, i.e. $111^{333} \equiv  6 ~(mod ~7)$. This gives that $6$ is a remainder when $111^{333}$ is divided by $7$. We have $333 \equiv 4 ~(mod ~7)$.  By property $6.$ of Theorem , we have $333^2 \equiv 4^2 \equiv 2 ~(mod ~7)$. Again, with the help of property $6.$ of Theorem , we have  $(333^2)^3 = 333^6 \equiv 2^3 \equiv 1 ~(mod ~7)$. We ca...

Example : Show that the integer $53^{103} + 103^{53}$ is divisible by $39$.  Answer: Firstly, we will find the remainder when $53^{103} $ and $ 103^{53}$ is divided by $39$. Then with help of property $4.$ of Theorem , we show that  the integer $53^{103} + 103^{53}$ is divisible by $39$. We have $53 \equiv 14 ~(mod ~39)$. By property $6.$ of Theorem , we have $53^2 \equiv 14^2 \equiv 1 ~(mod ~39)$. We can write $103$ as $103 = 51 \cdot 2 + 1$. Therefore $53^{103} \equiv (53^{2})^{51} \cdot 53 \equiv 1^{51} \cdot 53 \equiv  14 ~(mod ~39)$, i.e. $53^{103} \equiv  14 ~(mod ~39)$. This gives that $14$ is a remainder when $53^{103}$ is divided by $39$. We have $103 \equiv 25 ~(mod ~39)$. But $25 \equiv -14 ~ (mod ~ 39)$. Therefore $103 \equiv -14 ~(mod ~39)$. By property $6.$ of Theorem , we have $103^2 \equiv (- 14)^2 \equiv 1 ~(mod ~39)$.  We can write $53$ as $53 = 26 \cdot 2 + 1$. Therefore $103^{53} \equiv (103^{2})^{26} \cdot 103 \equiv 1^{26} \...

  Example: Find a remainder when $2^{50}$ is divided by $7$.  Answer: We have $2 \equiv 2 ~(mod ~7) $. By property $6.$ of Theorem ,  we have  $2^{2} \equiv 4 ~(mod ~7)$. On the same line we have $2^{3} \equiv 1 ~(mod ~7)$. We can write $50$ as $50 = 16 \cdot 3 + 2$. Therefore $2^{50} \equiv (2^{3})^{16} \cdot 2^2 \equiv 1^{48} \cdot 2^2 \equiv  4 ~(mod ~7)$, i.e. $2^{50} \equiv  4 ~(mod ~7)$. This gives that $4$ is a remainder when $2^{50}$ is divided by $7$. Example:   Find a remainder when $41^{65}$ is divided by $7$.   Answer: We have $41 \equiv 6 ~(mod ~7) $, but $6 \equiv -1 ~(mod ~7) $. Therefore $41 \equiv -1 ~(mod ~7) $. By property $6.$ of Theorem ,  we have  $41^{2} \equiv 1 ~(mod ~7)$.  We can write $65$ as $65 = 32 \cdot 2 + 1$. Therefore $41^{65} \equiv (41^{2})^{32} \cdot 41 \equiv 1^{32} \cdot 41 \equiv  6 ~(mod ~7)$, i.e. $41^{65} \equiv  6 ~(mod ~7)$. This gives that $6$ is a remainder whe...

 Let $a, ~b$ and $c$ be given integers. Then 1. If $a \mid b$, then $ a \mid b \cdot c$. 2. If  $a \mid b$ and $a \mid c$, then $ a^2 \mid b \cdot c$. 3.  $a \mid b$ if and only if $a \cdot c \mid b \cdot c$, where $c \not = 0$.  Answer: $1.$ Suppose that $a \mid b$. Therefore there exists an integer $d$ such that $b = a \cdot d$. Multiply $b = a \cdot d$ by $c$, so we get $b \cdot c = a \cdot c \cdot d $, where $c \cdot d$ is an integer. This gives $a \mid b \cdot c$. $2.$ Suppose that $a \mid b$ and $a \mid c$. So by $3$ of Theorem , we get $ a^2 \mid b \cdot c$. $3.$ Suppose that $a \mid b$. Therefore there exists an integer $d$ such that $b = a \cdot d$. Put $b = a \cdot d$ in $b \cdot c$, where $c \not = 0$ so $b \cdot c = a \cdot d \cdot c = (a \cdot c ) \cdot d$. This gives that $a \cdot c \mid b \cdot c$. Conversely suppose that $a \cdot c \mid b \cdot c$, where $c \not = 0$. Therefore there exists an integer $d$ such that $b \cdo...

 If $a \mid b$, show that $(- a ) \mid b, ~ a \mid (- b), $ and $ (- a ) \mid (- b)$.  Answer: Suppose that $a \mid b$. So there exists an integer $c$ such that $b = a \cdot c$.  We can write $b = a \cdot c$ as $b = (- a) \cdot (- c)$, where $(-a), ~ (-c)$ are integers. This gives $(- a ) \mid b$. Now multiply $b = a \cdot c$ by $(-1)$, we will have either $(- b) = a \cdot (- c)$, where $- c$ is an integer or $(- b) = (- a) \cdot c$, where $ c$ is an integer . This gives  $a  \mid (- b)$ or $ (- a ) \mid (- b)$. Therefore we have $(- a ) \mid b, ~ a \mid (- b), $ and $ (- a ) \mid (- b)$.

  Lemma:   If $a ~|~ b \cdot c$, with $ gcd(a, b) = 1$, then $a ~|~ c$. Proof:  Since $gcd(a, b) = 1$, by Theorem , there exist integers $x$ and $y$ such that $a \cdot x + b \cdot y = 1$. Multiplying this equation by $c$, we get  $c = c \cdot 1 = c~(a \cdot x + b \cdot y) = a \cdot c \cdot x + b \cdot c \cdot y$. As $ a ~|~ a \cdot c$ and  $ a ~|~ b \cdot c$, by part $7.$ of Theorem , $d ~|~ (a \cdot c \cdot x + b \cdot c \cdot y)$. Therefore $d ~|~ c$.

Corollary: If $a$ and $b$ are any integers, not both them are zero, then the set  $T = \{a \cdot x+ b \cdot y \;|\; x, y \in \mathbb{Z}\}$ is the set of all multiples of $d = gcd(a,b)$. Proof:  Since $d = gcd(a,b)$, we have  $d ~|~ a$ and $d ~|~ b$. By part $7.$ of Theorem ,  $d ~|~ (a \cdot x + b  \cdot y)$ for all integers $x, ~y$. Thus, every member of $T$ is a multiple of $d$. Conversely, Since $d = gcd(a,b)$,With the help of   Theorem , there exist integers $x'$ and $y'$ such that $gcd(a, b) =a \cdot x'+ b \cdot y'$. So that any multiple $n \cdot d$ of $d$ is of the form $n \cdot d = n~(a \cdot x' + b \cdot y') = a~(n \cdot x') + b~(n \cdot y')$. Hence, $n\cdot d$ is a linear combination of $a$ and $b$, and hence lies in $T$.

Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$  is not divisible by $a$. Theorem: For integers $a, ~b, ~c$ the following hold: $1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $. $2.$  $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$. $3.$  If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$. $4.$   If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$. $5.$  If $a ~|~ b$ and $b ~|~ a$ if and only if $a =  b$ or $a = -b$. $6.$  If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$. $7.$  If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$. Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Theref...