Solving a congruence/modular equation : $(((ax) mod M) + b) mod M = (ax + b) mod M$

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

I've been trying to prove this equation for my homework.

$$(((ax) bmod M) + b) mod M = (ax + b) bmod M$$

We have that $a,x,b,M > 0$, and $a ≡ b pmod M$

Reading KhanAcademy website, I found the following properties that looked promising.

 - Multiplication property : 
[(A * B) mod C = (A mod C * B mod C) mod C]
 - Addition property :
[(A + B) mod C = (A mod C + B mod C) mod C]

I tried developping the left side of the Equation :

$(((ax) bmod M) + b) bmod M rightarrow((a bmod M cdot x bmod M) bmod M + b) bmod M$ (multiplication property)

And if I develop the right side of the Equation :

$$(ax + b) bmod M = (ax bmod M + b bmod M) mod M$$ (addition property)

Which gives this after applying the multiplication property :

$$(((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

So I have

$$((abmod Mcdot x bmod M)bmod M+b) bmod M = (((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

It's almost the answer, but one side has $b bmod M$ and the other only has $b.$ I've been looking for more congruence properties but I can't seem to find one that would allow me to solve my problem. Have I been tackling this problem from the correct angle? Or did I make a mistake from the beginning (by applying the addition and multiplication properties)?

Any help would be greatly appreciated! Thanks

modular-arithmetic congruence-relations

share|cite|improve this question

edited Jul 18 at 4:57

Michael Hardy

204k23186462

asked Jul 18 at 2:41

Robert

6

add a comment | 

up vote
0
down vote

favorite

I've been trying to prove this equation for my homework.

$$(((ax) bmod M) + b) mod M = (ax + b) bmod M$$

We have that $a,x,b,M > 0$, and $a ≡ b pmod M$

Reading KhanAcademy website, I found the following properties that looked promising.

 - Multiplication property : 
[(A * B) mod C = (A mod C * B mod C) mod C]
 - Addition property :
[(A + B) mod C = (A mod C + B mod C) mod C]

I tried developping the left side of the Equation :

$(((ax) bmod M) + b) bmod M rightarrow((a bmod M cdot x bmod M) bmod M + b) bmod M$ (multiplication property)

And if I develop the right side of the Equation :

$$(ax + b) bmod M = (ax bmod M + b bmod M) mod M$$ (addition property)

Which gives this after applying the multiplication property :

$$(((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

So I have

$$((abmod Mcdot x bmod M)bmod M+b) bmod M = (((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

It's almost the answer, but one side has $b bmod M$ and the other only has $b.$ I've been looking for more congruence properties but I can't seem to find one that would allow me to solve my problem. Have I been tackling this problem from the correct angle? Or did I make a mistake from the beginning (by applying the addition and multiplication properties)?

Any help would be greatly appreciated! Thanks

modular-arithmetic congruence-relations

share|cite|improve this question

edited Jul 18 at 4:57

Michael Hardy

204k23186462

asked Jul 18 at 2:41

Robert

6

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

I've been trying to prove this equation for my homework.

$$(((ax) bmod M) + b) mod M = (ax + b) bmod M$$

We have that $a,x,b,M > 0$, and $a ≡ b pmod M$

Reading KhanAcademy website, I found the following properties that looked promising.

 - Multiplication property : 
[(A * B) mod C = (A mod C * B mod C) mod C]
 - Addition property :
[(A + B) mod C = (A mod C + B mod C) mod C]

I tried developping the left side of the Equation :

$(((ax) bmod M) + b) bmod M rightarrow((a bmod M cdot x bmod M) bmod M + b) bmod M$ (multiplication property)

And if I develop the right side of the Equation :

$$(ax + b) bmod M = (ax bmod M + b bmod M) mod M$$ (addition property)

Which gives this after applying the multiplication property :

$$(((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

So I have

$$((abmod Mcdot x bmod M)bmod M+b) bmod M = (((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

It's almost the answer, but one side has $b bmod M$ and the other only has $b.$ I've been looking for more congruence properties but I can't seem to find one that would allow me to solve my problem. Have I been tackling this problem from the correct angle? Or did I make a mistake from the beginning (by applying the addition and multiplication properties)?

Any help would be greatly appreciated! Thanks

modular-arithmetic congruence-relations

share|cite|improve this question

edited Jul 18 at 4:57

Michael Hardy

204k23186462

asked Jul 18 at 2:41

Robert

6

I've been trying to prove this equation for my homework.

$$(((ax) bmod M) + b) mod M = (ax + b) bmod M$$

We have that $a,x,b,M > 0$, and $a ≡ b pmod M$

Reading KhanAcademy website, I found the following properties that looked promising.

 - Multiplication property : 
[(A * B) mod C = (A mod C * B mod C) mod C]
 - Addition property :
[(A + B) mod C = (A mod C + B mod C) mod C]

I tried developping the left side of the Equation :

$(((ax) bmod M) + b) bmod M rightarrow((a bmod M cdot x bmod M) bmod M + b) bmod M$ (multiplication property)

And if I develop the right side of the Equation :

$$(ax + b) bmod M = (ax bmod M + b bmod M) mod M$$ (addition property)

Which gives this after applying the multiplication property :

$$(((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

So I have

$$((abmod Mcdot x bmod M)bmod M+b) bmod M = (((a bmod M cdot x bmod M)bmod M) + b bmod M) bmod M$$

It's almost the answer, but one side has $b bmod M$ and the other only has $b.$ I've been looking for more congruence properties but I can't seem to find one that would allow me to solve my problem. Have I been tackling this problem from the correct angle? Or did I make a mistake from the beginning (by applying the addition and multiplication properties)?

Any help would be greatly appreciated! Thanks

modular-arithmetic congruence-relations

share|cite|improve this question

edited Jul 18 at 4:57

Michael Hardy

204k23186462

asked Jul 18 at 2:41

Robert

6

share|cite|improve this question

share|cite|improve this question

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

204k23186462

asked Jul 18 at 2:41

Robert

6

asked Jul 18 at 2:41

Robert

6

asked Jul 18 at 2:41

Robert

6

6

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
1
down vote

Observe that $(a bmod M) bmod M = a bmod M$

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 2:44

debanjana

375111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for pointing it out!
  – Robert
  Jul 19 at 3:22
  

  
  
  
  

add a comment | 

up vote
0
down vote

$(((ax)bmod M) +b)bmod Mequiv ((ax)bmod M)bmod M +(bbmod M)$ then use debanjana's hint.

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for the tip! I think I got the answer!
  – Robert
  Jul 19 at 3:23
  

  
  
  
  

add a comment | 

up vote
0
down vote

It should be a basic property that you have proven and know like the back of your hand that

1) $(acirc b)mod M = ((amod M)circ (bmod M))mod M$ if $circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0le a' < M;$ and $b=b' + jM; 0le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)mod M = c = (a'+b')mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)mod M =c= (a'-b')mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)mod M = c= (a'b')mod M$.

2) And even more basic and obvious $(a mod M) mod M= amod M$.

Pf: If $a = a' + kM$ so $amod M =a'$ then $a' = a' + 0*M$ so $a' mod M = a'$.

.....
So

So $(ax + b) mod M = ((ax mod M) + (bmod M))mod M$

And $((axmod M) + b )mod M = (((ax mod M) mod M) + bmod M)mod M= ((ax mod M) +(bmod M)) mod M$.

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855137%2fsolving-a-congruence-modular-equation-ax-mod-m-b-mod-m-ax-b%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

Observe that $(a bmod M) bmod M = a bmod M$

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 2:44

debanjana

375111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for pointing it out!
  – Robert
  Jul 19 at 3:22
  

  
  
  
  

add a comment | 

up vote
1
down vote

Observe that $(a bmod M) bmod M = a bmod M$

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 2:44

debanjana

375111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for pointing it out!
  – Robert
  Jul 19 at 3:22
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Observe that $(a bmod M) bmod M = a bmod M$

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 2:44

debanjana

375111

Observe that $(a bmod M) bmod M = a bmod M$

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 2:44

debanjana

375111

share|cite|improve this answer

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

204k23186462

answered Jul 18 at 2:44

debanjana

375111

answered Jul 18 at 2:44

debanjana

375111

answered Jul 18 at 2:44

debanjana

375111

375111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for pointing it out!
  – Robert
  Jul 19 at 3:22
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for pointing it out!
  – Robert
  Jul 19 at 3:22
  

  
  
  
  

Thanks for pointing it out!
– Robert
Jul 19 at 3:22

Thanks for pointing it out!
– Robert
Jul 19 at 3:22

add a comment | 

up vote
0
down vote

$(((ax)bmod M) +b)bmod Mequiv ((ax)bmod M)bmod M +(bbmod M)$ then use debanjana's hint.

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for the tip! I think I got the answer!
  – Robert
  Jul 19 at 3:23
  

  
  
  
  

add a comment | 

up vote
0
down vote

$(((ax)bmod M) +b)bmod Mequiv ((ax)bmod M)bmod M +(bbmod M)$ then use debanjana's hint.

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for the tip! I think I got the answer!
  – Robert
  Jul 19 at 3:23
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

$(((ax)bmod M) +b)bmod Mequiv ((ax)bmod M)bmod M +(bbmod M)$ then use debanjana's hint.

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

$(((ax)bmod M) +b)bmod Mequiv ((ax)bmod M)bmod M +(bbmod M)$ then use debanjana's hint.

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

share|cite|improve this answer

share|cite|improve this answer

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

edited Jul 18 at 4:57

Michael Hardy

204k23186462

204k23186462

answered Jul 18 at 3:12

TheLast Cipher

538414

answered Jul 18 at 3:12

TheLast Cipher

538414

answered Jul 18 at 3:12

TheLast Cipher

538414

538414

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for the tip! I think I got the answer!
  – Robert
  Jul 19 at 3:23
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for the tip! I think I got the answer!
  – Robert
  Jul 19 at 3:23
  

  
  
  
  

Thanks for the tip! I think I got the answer!
– Robert
Jul 19 at 3:23

Thanks for the tip! I think I got the answer!
– Robert
Jul 19 at 3:23

add a comment | 

up vote
0
down vote

It should be a basic property that you have proven and know like the back of your hand that

1) $(acirc b)mod M = ((amod M)circ (bmod M))mod M$ if $circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0le a' < M;$ and $b=b' + jM; 0le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)mod M = c = (a'+b')mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)mod M =c= (a'-b')mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)mod M = c= (a'b')mod M$.

2) And even more basic and obvious $(a mod M) mod M= amod M$.

Pf: If $a = a' + kM$ so $amod M =a'$ then $a' = a' + 0*M$ so $a' mod M = a'$.

.....
So

So $(ax + b) mod M = ((ax mod M) + (bmod M))mod M$

And $((axmod M) + b )mod M = (((ax mod M) mod M) + bmod M)mod M= ((ax mod M) +(bmod M)) mod M$.

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

add a comment | 

up vote
0
down vote

It should be a basic property that you have proven and know like the back of your hand that

1) $(acirc b)mod M = ((amod M)circ (bmod M))mod M$ if $circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0le a' < M;$ and $b=b' + jM; 0le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)mod M = c = (a'+b')mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)mod M =c= (a'-b')mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)mod M = c= (a'b')mod M$.

2) And even more basic and obvious $(a mod M) mod M= amod M$.

Pf: If $a = a' + kM$ so $amod M =a'$ then $a' = a' + 0*M$ so $a' mod M = a'$.

.....
So

So $(ax + b) mod M = ((ax mod M) + (bmod M))mod M$

And $((axmod M) + b )mod M = (((ax mod M) mod M) + bmod M)mod M= ((ax mod M) +(bmod M)) mod M$.

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

add a comment | 

up vote
0
down vote

up vote
0
down vote

It should be a basic property that you have proven and know like the back of your hand that

1) $(acirc b)mod M = ((amod M)circ (bmod M))mod M$ if $circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0le a' < M;$ and $b=b' + jM; 0le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)mod M = c = (a'+b')mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)mod M =c= (a'-b')mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)mod M = c= (a'b')mod M$.

2) And even more basic and obvious $(a mod M) mod M= amod M$.

Pf: If $a = a' + kM$ so $amod M =a'$ then $a' = a' + 0*M$ so $a' mod M = a'$.

.....
So

So $(ax + b) mod M = ((ax mod M) + (bmod M))mod M$

And $((axmod M) + b )mod M = (((ax mod M) mod M) + bmod M)mod M= ((ax mod M) +(bmod M)) mod M$.

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

It should be a basic property that you have proven and know like the back of your hand that

1) $(acirc b)mod M = ((amod M)circ (bmod M))mod M$ if $circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0le a' < M;$ and $b=b' + jM; 0le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)mod M = c = (a'+b')mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)mod M =c= (a'-b')mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)mod M = c= (a'b')mod M$.

2) And even more basic and obvious $(a mod M) mod M= amod M$.

Pf: If $a = a' + kM$ so $amod M =a'$ then $a' = a' + 0*M$ so $a' mod M = a'$.

.....
So

So $(ax + b) mod M = ((ax mod M) + (bmod M))mod M$

And $((axmod M) + b )mod M = (((ax mod M) mod M) + bmod M)mod M= ((ax mod M) +(bmod M)) mod M$.

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 5:18

fleablood

60.5k22575

answered Jul 18 at 5:18

fleablood

60.5k22575

answered Jul 18 at 5:18

fleablood

60.5k22575

60.5k22575

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855137%2fsolving-a-congruence-modular-equation-ax-mod-m-b-mod-m-ax-b%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email