-2
$\begingroup$

Can anyone help me to prove this property used in the RSA correctness theorem?

$a^b\bmod{n}\equiv (a\bmod{n})^b\bmod{n}$

Specifically, here is what I have done:

enter image description here

this is what i mean. i can't understand this proof. With [] i mean binomial coefficient.

Can anyone help me to understand this?

$\endgroup$
7
  • 2
    $\begingroup$ How far did you get in the proof? Under what assumptions? Where did you get stuck? $\endgroup$ Commented Feb 24, 2015 at 17:13
  • $\begingroup$ no claim, I have to show the property to use it in the theorem of correctness of rsa $\endgroup$ Commented Feb 24, 2015 at 17:15
  • 1
    $\begingroup$ To add to what Gilles said, how are we suppose to "help" you if we don't know where you are stuck? Are you expecting someone to just answer it for you? $\endgroup$
    – mikeazo
    Commented Feb 24, 2015 at 17:15
  • $\begingroup$ i'm going to write my proof step by step First step : (a mod n)^{b} mod n = a^{b} mod n \exists k : a= kn+(a mod n) (a mod n)^{b} = [kn+(a mod n) ]^{k} mod n $\endgroup$ Commented Feb 24, 2015 at 17:31
  • $\begingroup$ I can tell you this, based on the updated image showing your work on the proof, you are headed in an unnecessarily complex direction (in my opinion). You should be able to do the proof given the hints I put below and simple algebra. $\endgroup$
    – mikeazo
    Commented Feb 24, 2015 at 18:42

3 Answers 3

1
$\begingroup$

$$\pi\colon\;\mathbb Z\to \mathbb Z/n\mathbb Z,\;a\mapsto a+n\mathbb Z$$ is a ring homomorphism.

$\endgroup$
1
$\begingroup$

Since you only ask for help, help is what I will give. I will not solve it for you, however. That said, since you didn't give an indication of where you are stuck, it is hard to help. Hopefully this helps.

If you can show that $(a\bmod{n}\cdot c\bmod{n})\bmod{n} \equiv (a\cdot c)\bmod{n}$, for all $a,c\in\mathbb{Z}_n^*$, then you can show the property you are interested in.

What does it mean for two things to be equivalent modulo $n$? We say that $a \equiv k\bmod{n}$ if $a=c\cdot n + k$ for some integer value $c$. Use this to show that the two things I listed are equivalent. The relationship you are interested in follows from that. Notice that $(a\bmod{n})^2 \bmod{n} \equiv ((a\bmod{n})\cdot(a\bmod{n}))\bmod{n}$. You can do a similar thing with $b$ in the exponent, instead of $2$.

$\endgroup$
0
$\begingroup$

Let u = a mod n, i.e., the least residue modulo n. Then: a = u + k.n for some k in Z.

The binomial expansion of the exponential is: $$(u + kn)^{b} = \sum_{i = 0}^{b}\binom{b}{i}u^{b - i}(kn)^{i}$$

Every term, except for i = 0, is a multiple of (n), which is congruent to 0 mod n. The i = 0 term: (u^b), yields: (a mod n)^b.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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