Prove $forall a in mathbb{N}, forall b in mathbb{N}, ab text{ mod } n = (a text{ mod } n)(b text{ mod } n)...

This question already has an answer here:

Product Rule for the mod operator

2 answers

Please prove $forall a in mathbb{N}, forall b in mathbb{N}, ab text{ mod } n = (a text{ mod } n)(b text{ mod } n) text{ mod } n$. I have been stuck on this problem for quite a while now. I have no idea how to approach this problem. Alongside proving this, can someone please give me advice as to how I should tackle these types of proofs.

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

marked as duplicate by Bill Dubuque, Lord Shark the Unknown, Rebellos, Jyrki Lahtonen, Lee David Chung Lin Dec 4 '18 at 21:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1

$(amod n)(bmod n)mod n$ has no sense...
– Surb
Dec 4 '18 at 16:08

1

@Surb Why not? $amod n$ and $bmod n$ are natural numbers.
– mfl
Dec 4 '18 at 16:12

1

@mfl: Let denote $[a]$ for $(amod n)$. Then $[a]$ is an equivalence class, not a natural number. If for you $[a]mod n$ make sense, you should tel me which one... in one side you have an element of $mathbb Z/_sim$ and on the other hand an relation on $mathbb Z$...
– Surb
Dec 4 '18 at 16:21

@Surb I agree. But if $a,ninmathbb N$ you can identify $amod n$ with the smallest element of the equivalence class and thus you get a natural number.
– mfl
Dec 4 '18 at 16:22

@mfl: indeed we understand... but why not writing it correctly from the beginning instead of writing something wrong and suppose what it could be ?
– Surb
Dec 4 '18 at 16:32

|
show 1 more comment

This question already has an answer here:

Product Rule for the mod operator

2 answers

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

marked as duplicate by Bill Dubuque, Lord Shark the Unknown, Rebellos, Jyrki Lahtonen, Lee David Chung Lin Dec 4 '18 at 21:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1

$(amod n)(bmod n)mod n$ has no sense...
– Surb
Dec 4 '18 at 16:08

1

@Surb Why not? $amod n$ and $bmod n$ are natural numbers.
– mfl
Dec 4 '18 at 16:12

1

@mfl: Let denote $[a]$ for $(amod n)$. Then $[a]$ is an equivalence class, not a natural number. If for you $[a]mod n$ make sense, you should tel me which one... in one side you have an element of $mathbb Z/_sim$ and on the other hand an relation on $mathbb Z$...
– Surb
Dec 4 '18 at 16:21

@Surb I agree. But if $a,ninmathbb N$ you can identify $amod n$ with the smallest element of the equivalence class and thus you get a natural number.
– mfl
Dec 4 '18 at 16:22

@mfl: indeed we understand... but why not writing it correctly from the beginning instead of writing something wrong and suppose what it could be ?
– Surb
Dec 4 '18 at 16:32

|
show 1 more comment

This question already has an answer here:

Product Rule for the mod operator

2 answers

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

This question already has an answer here:

Product Rule for the mod operator

2 answers

This question already has an answer here:

Product Rule for the mod operator

2 answers

elementary-number-theory discrete-mathematics

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

edited Dec 4 '18 at 18:18

Bill Dubuque

209k29190629

asked Dec 4 '18 at 16:01

Noobcoder

274

asked Dec 4 '18 at 16:01

Noobcoder

274

asked Dec 4 '18 at 16:01

Noobcoder

274

marked as duplicate by Bill Dubuque, Lord Shark the Unknown, Rebellos, Jyrki Lahtonen, Lee David Chung Lin Dec 4 '18 at 21:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

marked as duplicate by Bill Dubuque, Lord Shark the Unknown, Rebellos, Jyrki Lahtonen, Lee David Chung Lin Dec 4 '18 at 21:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1

$(amod n)(bmod n)mod n$ has no sense...
– Surb
Dec 4 '18 at 16:08

1

@Surb Why not? $amod n$ and $bmod n$ are natural numbers.
– mfl
Dec 4 '18 at 16:12

1

@mfl: Let denote $[a]$ for $(amod n)$. Then $[a]$ is an equivalence class, not a natural number. If for you $[a]mod n$ make sense, you should tel me which one... in one side you have an element of $mathbb Z/_sim$ and on the other hand an relation on $mathbb Z$...
– Surb
Dec 4 '18 at 16:21

@Surb I agree. But if $a,ninmathbb N$ you can identify $amod n$ with the smallest element of the equivalence class and thus you get a natural number.
– mfl
Dec 4 '18 at 16:22

@mfl: indeed we understand... but why not writing it correctly from the beginning instead of writing something wrong and suppose what it could be ?
– Surb
Dec 4 '18 at 16:32

|
show 1 more comment

1

$(amod n)(bmod n)mod n$ has no sense...
– Surb
Dec 4 '18 at 16:08

1

@Surb Why not? $amod n$ and $bmod n$ are natural numbers.
– mfl
Dec 4 '18 at 16:12

1

@mfl: Let denote $[a]$ for $(amod n)$. Then $[a]$ is an equivalence class, not a natural number. If for you $[a]mod n$ make sense, you should tel me which one... in one side you have an element of $mathbb Z/_sim$ and on the other hand an relation on $mathbb Z$...
– Surb
Dec 4 '18 at 16:21

@Surb I agree. But if $a,ninmathbb N$ you can identify $amod n$ with the smallest element of the equivalence class and thus you get a natural number.
– mfl
Dec 4 '18 at 16:22

@mfl: indeed we understand... but why not writing it correctly from the beginning instead of writing something wrong and suppose what it could be ?
– Surb
Dec 4 '18 at 16:32

$(amod n)(bmod n)mod n$ has no sense...
– Surb
Dec 4 '18 at 16:08

@Surb Why not? $amod n$ and $bmod n$ are natural numbers.
– mfl
Dec 4 '18 at 16:12

@mfl: Let denote $[a]$ for $(amod n)$. Then $[a]$ is an equivalence class, not a natural number. If for you $[a]mod n$ make sense, you should tel me which one... in one side you have an element of $mathbb Z/_sim$ and on the other hand an relation on $mathbb Z$...
– Surb
Dec 4 '18 at 16:21

@Surb I agree. But if $a,ninmathbb N$ you can identify $amod n$ with the smallest element of the equivalence class and thus you get a natural number.
– mfl
Dec 4 '18 at 16:22

@mfl: indeed we understand... but why not writing it correctly from the beginning instead of writing something wrong and suppose what it could be ?
– Surb
Dec 4 '18 at 16:32

|
show 1 more comment

2 Answers
2

active

oldest

votes

Let $x=a (text{mod} n), y=b (text{mod} n).$ Then for some integers $k,h$ the numbers $a,b$ decompose as $a=ncdot k+x, b=ncdot l+y.$

So, for this reason $$ab=(nk+x)(nl+y)=xy+nlx+nky+n^2lk=xy+n(lx+ky+nlk).$$

Therefore, $ab (text{mod} n)=xy=big(a (text{mod} n)cdot b (text{mod} n)big) (text{mod} n).$

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

add a comment |

Hint

Given $a,b,ninmathbb N$ there exist $c,d,r,sinmathbb N$ such that $a=c+rn, b=d+sn.$ And it is

$$ab=cd+(cs+rd+rsn)n.$$

answered Dec 4 '18 at 16:08

mfl

26k12141

add a comment |

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

Let $x=a (text{mod} n), y=b (text{mod} n).$ Then for some integers $k,h$ the numbers $a,b$ decompose as $a=ncdot k+x, b=ncdot l+y.$

So, for this reason $$ab=(nk+x)(nl+y)=xy+nlx+nky+n^2lk=xy+n(lx+ky+nlk).$$

Therefore, $ab (text{mod} n)=xy=big(a (text{mod} n)cdot b (text{mod} n)big) (text{mod} n).$

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

add a comment |

Let $x=a (text{mod} n), y=b (text{mod} n).$ Then for some integers $k,h$ the numbers $a,b$ decompose as $a=ncdot k+x, b=ncdot l+y.$

So, for this reason $$ab=(nk+x)(nl+y)=xy+nlx+nky+n^2lk=xy+n(lx+ky+nlk).$$

Therefore, $ab (text{mod} n)=xy=big(a (text{mod} n)cdot b (text{mod} n)big) (text{mod} n).$

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

add a comment |

Let $x=a (text{mod} n), y=b (text{mod} n).$ Then for some integers $k,h$ the numbers $a,b$ decompose as $a=ncdot k+x, b=ncdot l+y.$

So, for this reason $$ab=(nk+x)(nl+y)=xy+nlx+nky+n^2lk=xy+n(lx+ky+nlk).$$

Therefore, $ab (text{mod} n)=xy=big(a (text{mod} n)cdot b (text{mod} n)big) (text{mod} n).$

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

Let $x=a (text{mod} n), y=b (text{mod} n).$ Then for some integers $k,h$ the numbers $a,b$ decompose as $a=ncdot k+x, b=ncdot l+y.$

So, for this reason $$ab=(nk+x)(nl+y)=xy+nlx+nky+n^2lk=xy+n(lx+ky+nlk).$$

Therefore, $ab (text{mod} n)=xy=big(a (text{mod} n)cdot b (text{mod} n)big) (text{mod} n).$

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

edited Dec 4 '18 at 16:32

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

answered Dec 4 '18 at 16:09

Riccardo Ceccon

1,040321

add a comment |

Hint

Given $a,b,ninmathbb N$ there exist $c,d,r,sinmathbb N$ such that $a=c+rn, b=d+sn.$ And it is

$$ab=cd+(cs+rd+rsn)n.$$

answered Dec 4 '18 at 16:08

mfl

26k12141

add a comment |

Hint

Given $a,b,ninmathbb N$ there exist $c,d,r,sinmathbb N$ such that $a=c+rn, b=d+sn.$ And it is

$$ab=cd+(cs+rd+rsn)n.$$

answered Dec 4 '18 at 16:08

mfl

26k12141

add a comment |

Hint

Given $a,b,ninmathbb N$ there exist $c,d,r,sinmathbb N$ such that $a=c+rn, b=d+sn.$ And it is

$$ab=cd+(cs+rd+rsn)n.$$

answered Dec 4 '18 at 16:08

mfl

26k12141

Hint

Given $a,b,ninmathbb N$ there exist $c,d,r,sinmathbb N$ such that $a=c+rn, b=d+sn.$ And it is

$$ab=cd+(cs+rd+rsn)n.$$

answered Dec 4 '18 at 16:08

mfl

26k12141

answered Dec 4 '18 at 16:08

mfl

26k12141

answered Dec 4 '18 at 16:08

mfl

26k12141

answered Dec 4 '18 at 16:08

mfl

26k12141

add a comment |

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Htykuut