Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 4 of 4
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,749
    Thanks
    2,195 times
    Thanked
    693 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #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. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,749
    Thanks
    2,195 times
    Thanked
    693 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #2 Thread Author
    Quote Originally Posted by mathmari View Post
    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?
    Last edited by mathmari; December 7th, 2016 at 13:03.

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,270
    Thanks
    514 times
    Thanked
    4,166 times
    Thank/Post
    1.835
    Awards
    MHB Chat Room Award (2016)  

MHB Humor Award (2016)  

MHB Discrete Mathematics Award (2016)  

MHB Best Ideas Award (2015)  

MHB Discrete Mathematics Award (2015)
    #3
    Quote Originally Posted by mathmari View Post
    What is an inductive definition?
    Is there a reason why you can't look this up in your lecture notes or textbook? Or see .

    Quote Originally Posted by mathmari View Post
    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.

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

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,749
    Thanks
    2,195 times
    Thanked
    693 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #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?

Similar Threads

  1. Exercise with modulo
    By mathmari in forum Linear and Abstract Algebra
    Replies: 5
    Last Post: June 23rd, 2014, 23:47
  2. [SOLVED] Matrix multiplication simplified to Vector multiplication
    By CyanBC in forum Other Topics
    Replies: 2
    Last Post: March 18th, 2014, 22:45
  3. Primitive root modulo 169
    By tda120 in forum Number Theory
    Replies: 4
    Last Post: November 4th, 2013, 17:03
  4. Diophantine equation, modulo
    By Petrus in forum Number Theory
    Replies: 6
    Last Post: April 22nd, 2013, 20:46
  5. Find 'n' in modulo equation
    By Albert in forum Challenge Questions and Puzzles
    Replies: 7
    Last Post: January 29th, 2013, 23:35

Tags for this Thread

Posting Permissions

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