-1
$\begingroup$

If $x\equiv 1 \mod 3$, then $x^{100}\equiv 1 \mod 3$.

I need an explanation on this. If possible an answer would be more appreciable.

$\endgroup$

closed as off-topic by Najib Idrissi, Namaste, user88595, hardmath, Hakim Jun 8 '14 at 13:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Najib Idrissi, Namaste, user88595, hardmath, Hakim
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What you need is what you get, yeah? Not always:( Show you effort first:) $\endgroup$ – Vladimir Jun 8 '14 at 11:34
  • $\begingroup$ I read a book one time that said something like "Congruences can be added and multiplied just like ordinary integers." To me, that made more sense than all the lines of formulas I've seen in other books. For example, what's $2 \times 2 \mod 3$? What's $2^3 \mod 3$? In fact, compute the first twenty powers of 2 modulo 3. I think that will probably put things in much sharper perspective for you than anything else I can say. $\endgroup$ – Robert Soupe Jun 8 '14 at 16:55
4
$\begingroup$

Suppose that $x = 1\text{ (mod 3)}$, it means that there exists an integer $k$ such that $x=3k+1$. Now, if we multiply $x$ by $x$, we have $$ x^2 = (3k+1)(3k+1) = 9k^2+6k+1 = 3l+1 $$ where $l=3k^2+2k$ is an integer. It means that $x^2 = 1\text{ (mod 3)}$. Knowing this, can you guess if $x^{100} = 1\text{ (mod 3)}$ or not?

$\endgroup$
  • $\begingroup$ so it is true then $\endgroup$ – Kartik Jun 8 '14 at 11:36
  • $\begingroup$ Yes, I let you do a complete proof. $\endgroup$ – user37238 Jun 8 '14 at 11:37
  • $\begingroup$ umm about the proof. Thats where i have difficulties $\endgroup$ – Kartik Jun 8 '14 at 11:40
4
$\begingroup$

$$x \equiv 1 \pmod{3} $$ tells you that $x-1$ is a multiple of 3. Combine this with the fact that $$x^{100}-1=(x-1)(x^{99}+x^{98}+\dots+x). $$

$\endgroup$
3
$\begingroup$

Though one can give direct proofs, to become proficient at modular arithmetic it is essential to master the basic properties of congruences, so that modular arithmetic becomes almost as intuitive as ordinary integer arithmetic. The question at hand follows by a special case of the Congruence Power Rule (an inductive consequence of the Congruence Product Rule). Namely, $\ x\equiv 1\,\Rightarrow\,x^n\equiv 1^n\equiv 1\pmod m.\ $ See the proofs below.


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 applyimg the Polynomial Rule with $\,f(x) = x^{\rm b}).$

$\endgroup$
1
$\begingroup$

By what you gave we can say $x=3k+1;k\in \mathbb{Z}$ Now from the binomial theorem $$(3k+1)^n=\sum_{b=0}^n {n\choose b}(3k)^{n-b}1^b$$ From this the only term that doesn't have $3$ as a factor is when $n=b$ which is $(3k)^0\cdot1^n=1$ so any number raised to $n$ is equal(in mod) as it's remainder on that power,now take $n=100$ and Voila.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.