MHB Defining & Proving Modulo Multiplication in $\mathbb{Z}_k$

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Multiplication
AI Thread Summary
The discussion focuses on defining multiplication in the modular arithmetic system $\mathbb{Z}_k$ using an inductive approach. The proposed definition states that for non-negative integers, multiplication is defined as $x \cdot_k 0 = 0$ and $x \cdot_k (y+1) = x \cdot_k y +_k x$. Participants explore the validity of proving the equivalence $(x \cdot y) \mod k = (x \mod k) \cdot_k (y \mod k)$ through induction, questioning whether to apply induction on $y$. The base case and inductive step are outlined, demonstrating that both sides of the equation are equal under the defined operations. The conversation emphasizes the need for a clear inductive definition before proceeding with proofs.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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? (Wondering)

Do we write $x\cdot y=y+y+\ldots +y$ ($n$-times) and we apply each time the addition $+_k$ ? (Wondering)
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? (Wondering)
 
Mathematics news on Phys.org
mathmari said:
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? (Wondering)

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? (Wondering)
 
Last edited by a moderator:
mathmari said:
What is an inductive definition?
Is there a reason why you can't look this up in your lecture notes or textbook? Or see Wikipedia.

mathmari said:
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.

mathmari said:
Is the induction as follows?
Until there is a definition, it makes no sense to prove anything.
 
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? (Wondering)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Just chatting with my son about Maths and he casually mentioned that 0 would be the midpoint of the number line from -inf to +inf. I wondered whether it wouldn’t be more accurate to say there is no single midpoint. Couldn’t you make an argument that any real number is exactly halfway between -inf and +inf?
Back
Top