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,588
    Thanks
    2,073 times
    Thanked
    663 times
    Trophies
    1 Highscore
    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,588
    Thanks
    2,073 times
    Thanked
    663 times
    Trophies
    1 Highscore
    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,192
    Thanks
    510 times
    Thanked
    4,078 times
    Thank/Post
    1.860
    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,588
    Thanks
    2,073 times
    Thanked
    663 times
    Trophies
    1 Highscore
    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