I feel like I should know these concepts, but I don't.
Asked
Active
Viewed 136 times
2
-
1Note that $10$ is congruent to $1$. So $10^k$ is congruent to ? – André Nicolas Jul 26 '14 at 20:45
-
I know two integers a and b cab be congruent modulo n, but what does it mean for two integers to be congruent? – Erbolat Jul 26 '14 at 20:51
-
I was saving words. The modulus is $3$, I should have written that $10$ is congruent to $1$ modulo $3$. – André Nicolas Jul 26 '14 at 21:00
-
For further context see the OP's comment to their prior question. – Bill Dubuque Jul 26 '14 at 21:11
2 Answers
0
Partial answer:
$X \pmod Y$ is the remainder of dividing integer $X$ by integer $Y$
So $X \pmod Y$ is equal to some integer value between $0$ and $Y-1$
Having said that, $X^k \pmod Y$ is equal to $[X \pmod Y]^k \pmod Y$
So $10^k\pmod3\equiv[10\pmod3]^k\pmod3\equiv1^k\pmod3\equiv1\pmod3=1$
barak manos
- 43,109
-
$1 \pmod 3$ = $1$. $\frac 13$ doesnt leave a remainder of 1. Can you elaborate on that? – Erbolat Jul 26 '14 at 21:06
-
@Erbolat: In order to calculate $1\bmod3$: Divide $1$ by $3$. The number you get is made of an integer part and a fraction part. In this case, the integer part is $0$ and the fraction part $\frac{1}{3}$. You can throw away the integer part. Now, you take the fraction part, and you multiply it by $3$. The result of what you get is the answer to your question. In this case, $\frac{1}{3}\cdot3=1$, therefore $1\bmod3=1$. Let's do it again with $19\bmod7$: First, $\frac{19}{7}=2\frac{5}{7}$. Throw away $2$ and calculate $\frac{5}{7}\cdot7=5$. Therefore, $19\bmod7=5$. – barak manos Jul 27 '14 at 06:02
0
Hint $\ n = a_k 10^k + \cdots + a_1 10 + a_0 = f(10)\,$ is a polynomial $\,f\,$ in $10$ with integer coeff's $\,a_i.\,$ Therefore, $\,{\rm mod}\ 3\!:\ \color{#c00}{10\equiv 1}\,\Rightarrow\,f(\color{#c00}{10})\equiv f(\color{#c00}1) = a_k + \cdots + a_1 + a_0$ follows by applying the Polynomial Congruence Rule below. This is casting out threes, like casting out nines.
Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$
Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $
Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$
Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $
Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$
Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$
Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$
Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, \color{#0a0}{A g(A)\equiv a g(a)}\,$ by the Product Rule. Hence $\,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$ by the Sum Rule.
Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv\, a^b$ is not generally true (unless $\rm B = b,\,$ so it follows by applying the Polynomial Rule with $\,f(x) = x^{\rm b}).$
Bill Dubuque
- 272,048