I have found out, that the following is true for modular arithmetic when $t$ is a natural number.
$$a^t \bmod\ n \equiv (a\bmod\ n)^t\bmod\ n$$
But I have been unable to find a proof for this, does anyone have a source that proves this conjecture?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Hint $$(a+cn)(b+dn)-ab=n(ad+bc+cdn).$$ $\endgroup$awllower– awllower2014-02-02 16:08:41 +00:00Commented Feb 2, 2014 at 16:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
Hint
$$a^t-b^t=(a-b)(a^{t-1}+a^{t-2}b+\cdots+ab^{t-2}+b^{t-1})$$
-
$\begingroup$ I'm afraid I don't understand. $$(a^{t−1}+a^{t−2}b+⋯+ab^{t−2}+b^{t−1})$$what pattern does it follow, ie. what is the "..."? $\endgroup$Clewett83– Clewett832014-02-02 16:19:33 +00:00Commented Feb 2, 2014 at 16:19
-
$\begingroup$ From the given equality if $n$ divides $a-b$ it divides also $a^t-b^t$. Right? $\endgroup$user63181– user631812014-02-02 16:23:10 +00:00Commented Feb 2, 2014 at 16:23
-
$\begingroup$ Yes, I'm with you on that. $\endgroup$Clewett83– Clewett832014-02-02 16:25:33 +00:00Commented Feb 2, 2014 at 16:25
-
$\begingroup$ So what's the meaning of $a\equiv b (mod \;n)$? $\endgroup$user63181– user631812014-02-02 16:26:39 +00:00Commented Feb 2, 2014 at 16:26
-
$\begingroup$ That's $$a\ mod\ n\ =\ b$$ right? $\endgroup$Clewett83– Clewett832014-02-02 16:29:19 +00:00Commented Feb 2, 2014 at 16:29
$\begingroup$
$\endgroup$
We want to prove $$a^t \bmod\ n \equiv (a\bmod\ n)^t\bmod\ n.$$ Let $ a \bmod n \equiv b $.
Thus by substitution we are proving $$a^t \bmod\ n \equiv b ^t\bmod\ n.$$ But this means we need to show $ n \mid a^t - b^t $ under the assumption that $ n \mid a - b $ .
Then using the fact that $a^t-b^t=(a-b)(a^{t-1}+a^{t-2}b+\cdots+ab^{t-2}+b^{t-1})$
