Multiplication in Zp is a much more complicated and interesting affair; in fact,

Question

Multiplication in Zp is a much more complicated and interesting affair; in fact, multiplication in Z is one of the basic mathematical structures that can give rise to rich cryptographic constructions. Recall that in Z. when a and b are both nonzero, ab is also nonzero. However, consider [31 and [5] in Z15. Then [3] X [51 = [15] = [OJ. A mathematician would say that Z!5 has zero-divisors. However, consider the Z7. It turns out that when [a] [0] and [b] [0] (in Z7). then [a] [b] = [ab] 0. To prove this, write down the entire multiplication table of Z7. (You can make a 7 X 7 table, and fill in the entries.) Use your table to prove the following: For every nonzero element [a] Z7. there is an clement [b] Z7 so that [ab] = [1]. This element is called the multiplicative inverse of [a].

Explanation / Answer

the equality is obviously on modulo(7),

it is clear from multiplication table that each non-zero a has multiplicative inverse.

for 2 you get its inverse to be 4,

for 3 its 5,

for 4 its 2,

for 6 its 6,

for 1 its 1..etc.

In advanced language Z7 is a field.

I also have a different proof which is more general and works for any prime and which avoid using multiplication table.

but for beginner its okk

1 2 3 4 5 6 7=0 in Z7 1 1 2 3 4 5 6 0 2 2 4 6 8=1 10=3 12=5 0 3 3 6 9=2 12=5 15=1 18=4 0 4 4 8=1 12=5 16=2 20=6 24=3 0 5 5 10=3 15=1 20=6 25=4 30=2 0 6 6 12=5 18=4 24=3 30=2 36=1 0 7=0 in Z7 0 0 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.