Modulo multiplication - inductive definition

212 Views Asked by At

Based on the definition of $+_k$, I want to give an inductive definition for the multiplication $\cdot_k$ in $\mathbb{Z}_k$, such that for all $x\in \mathbb{N}_0$ and $y\in \mathbb{N}_0$ it holds that $$x\cdot_k y=(x\cdot y)\mod k$$

What is an inductive definition?

Do we write $x\cdot y=y+y+\ldots +y$ ($n$-times) and we apply each time the addition $+_k$ ?

I want to prove also by induction that for a $x\in \mathbb{N}_0$ it holds for all $y\in \mathbb{N}_0$ that $$(x\cdot y)\mod k=(x\mod k)\cdot_k (y\mod k)$$

We apply the induction on $y$ or not?

1

There are 1 best solutions below

0
On BEST ANSWER

$x \cdot y = y + y + \dots + y$ (where there are $x$ terms in the summand) is not an inductive definition, since it does not define $\cdot$ in terms of smaller arguments.

$$x \cdot_k (y+1) = x \cdot_k y +_k x$$

To prove the second statement, I'd use the division algorithm. However, that's not explicitly inductive (though the proof of the division algorithm is), so yes, induct on $y$.