Thanks:  0

# Thread: Modulo multiplication

1. Hey!!

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?

2. Thread Author
Originally Posted by mathmari
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?
Is the induction as follows?

Base case: $y=1$ : $$(x\cdot 1)\mod k=x\mod k$$ The other side is $$(x\mod k)\cdot_k (1\mod k)=(x\mod k)\cdot_k 1=x\mod k$$ So, they are equal.

Inductive Hypothesis: We suppose that it holds for $y=n$ : $$(x\cdot n)\mod k=(x\mod k)\cdot_k(n\mod k)$$

Inductive step: We will show that it holds for $y=n+1$ : $$(x\cdot (n+1))\mod k=(x\cdot n+x)\mod k=(x\cdot n)\mod k+x\mod k \ \ \overset{\text{ Inductive Hypothesis } }{ = } \ \ (x\mod k)\cdot_k (n\mod k)+x\mod k$$ The other side is $$(x\mod k)\cdot_k ((n+1)\mod k)=(x\mod k)\cdot_k (n\mod k+1)\\ =(x\mod k)\cdot_k (n\mod k)+x\mod k$$ So, they are equal.

Is this correct? Could I improve something?

3. Originally Posted by mathmari
What is an inductive definition?
Is there a reason why you can't look this up in your lecture notes or textbook? Or see .

Originally Posted by mathmari
Do we write $x\cdot y=y+y+\ldots +y$ ($n$-times) and we apply each time the addition $+_k$ ?
No inductive definition uses ellipsis.

Originally Posted by mathmari
Is the induction as follows?
Until there is a definition, it makes no sense to prove anything.

4. Thread Author
An inductive definition for the multiplication $\cdot_k$ in $\mathbb{Z}_k$ is the following:
\begin{align*}&x\cdot_k 0=0 \\ &x\cdot_k (y+1)=x\cdot_k y+_kx, \ y\geq 0\end{align*}
right?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•