Fdtxjr

Print a physical multiplication table

Could any one tell what PN is this Chip? Thanks~

Have any astronauts/cosmonauts died in space?

Writing in a Christian voice

When should a starting writer get his own webpage?

How are passwords stolen from companies if they only store hashes?

Why doesn't the fusion process of the sun speed up?

Did Nintendo change its mind about 68000 SNES?

If I cast the Enlarge/Reduce spell on an arrow, what weapon could it count as?

Why I don't get the wanted width of tcbox?

How can an organ that provides biological immortality be unable to regenerate?

How do you justify more code being written by following clean code practices?

Why does Surtur say that Thor is Asgard's doom?

Why is participating in the European Parliamentary elections used as a threat?

What will the Frenchman say?

What is it called when someone votes for an option that's not their first choice?

What (if any) is the reason to buy in small local stores?

Recursively updating the MLE as new observations stream in

PTIJ: Why do we make a Lulav holder?

Should I be concerned about student access to a test bank?

How to balance a monster modification (zombie)?

Why is indicated airspeed rather than ground speed used during the takeoff roll?

Determine voltage drop over 10G resistors with cheap multimeter

"Marked down as someone wanting to sell shares." What does that mean?

Using Chinese Remainder Theorem for large modulo

Getting an X for Chinese Remainder Theorem (CRT)Extended Euclidean Algorithm and Chinese Remainder TheoremApplication of the Chinese Remainder TheoremHaving trouble using the Chinese Remainder Theorem to solve a system of congruencesCalculating powers of large number using Chinese Remainder TheoremIs this an application of the Chinese Remainder Theorem?Another Chinese Remainder Theorem ProblemUsing the Chinese Remainder Theorem to prove that a system of equations has a solution in $mathbbN$ if and only if certain conditions are metProof of Chinese Remainder TheoremReconciling two versions of Chinese Remainder TheoremIdeals and the Chinese Remainder Theorem

1

$begingroup$

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem:

Compute which element of $mathbbZ/2550mathbbZ$ under the map of the Chinese Remainder Theorem is mapped to $(bar14,bar32)$ in $mathbbZ/50mathbbZ timesmathbbZ/51mathbbZ$.

Now I think I should solve the following system:

$x=14 mod 50$

$x=32 mod 50$

$x=14 mod 51$

$x=32 mod 51,$
but if I attempt this using the 'general' CRT I have to compute very large multiplications (such as $50 cdot 50 cdot 51 cdot 51$) and since no calculator is used I think I'm on the wrong course.

Any suggestions how to handle this?

modular-arithmetic chinese-remainder-theorem

share|cite|improve this question

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For $, (bar 14,bar 32)in Bbb Z_large 50times Bbb Z_large 51$ you want $,xequiv 14pmod!50,,$ $,xequiv 32pmod!51,,$ not the other congruences. Where did they come from?
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:38
  
  

  
  
  
  

add a comment | 

1

$begingroup$

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem:

Compute which element of $mathbbZ/2550mathbbZ$ under the map of the Chinese Remainder Theorem is mapped to $(bar14,bar32)$ in $mathbbZ/50mathbbZ timesmathbbZ/51mathbbZ$.

Now I think I should solve the following system:

$x=14 mod 50$

$x=32 mod 50$

$x=14 mod 51$

$x=32 mod 51,$
but if I attempt this using the 'general' CRT I have to compute very large multiplications (such as $50 cdot 50 cdot 51 cdot 51$) and since no calculator is used I think I'm on the wrong course.

Any suggestions how to handle this?

modular-arithmetic chinese-remainder-theorem

share|cite|improve this question

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For $, (bar 14,bar 32)in Bbb Z_large 50times Bbb Z_large 51$ you want $,xequiv 14pmod!50,,$ $,xequiv 32pmod!51,,$ not the other congruences. Where did they come from?
  $endgroup$
  – Bill Dubuque
  Mar 13 at 21:38
  
  

  
  
  
  

add a comment | 

$begingroup$

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem:

Compute which element of $mathbbZ/2550mathbbZ$ under the map of the Chinese Remainder Theorem is mapped to $(bar14,bar32)$ in $mathbbZ/50mathbbZ timesmathbbZ/51mathbbZ$.

Now I think I should solve the following system:

$x=14 mod 50$

$x=32 mod 50$

$x=14 mod 51$

$x=32 mod 51,$
but if I attempt this using the 'general' CRT I have to compute very large multiplications (such as $50 cdot 50 cdot 51 cdot 51$) and since no calculator is used I think I'm on the wrong course.

Any suggestions how to handle this?

modular-arithmetic chinese-remainder-theorem

share|cite|improve this question

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

$endgroup$

share|cite|improve this question

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

share|cite|improve this question

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

edited Mar 13 at 10:22

José Carlos Santos

168k23132236

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

asked Mar 13 at 10:08

MathbeginnerMathbeginner

30718

2 Answers
2

active

oldest

votes

2

$begingroup$

A very simple way: $bmod (50,51)!:, (14,32)equiv 16(color#0a04,color#c002)to 16(color#90f104)=1664 $ since by Easy CRT

$quad beginalignx&equivcolor#0a0 4!!!pmod50\ x&equiv color#c002!!!pmod51endalign$ $iff xequivcolor#c00 2+51underbraceleft[dfraccolor#0a04-color#c00251bmod 50right]_Large equiv 2/1 !equiv color#90f104,pmod50cdot 51$

Remark $ $ Without factoring $, xequiv 51cdotcolor#0a014 - 50cdot color#c0032equiv 714! -! 1600equiv -886equiv 2550-886equiv 1664 $ hence the arithmetic is harder mentally without factoring out $16$ (or $32)$ at the start.

share|cite|improve this answer

edited Mar 14 at 13:37

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) Very nice!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, very nice. Never heard of the Easy CRT before.
  $endgroup$
  – Mathbeginner
  Mar 14 at 9:51
  

  
  
  
  

add a comment | 

2

$begingroup$

All you need to do is to solve the system$$left{beginarraylxequiv14pmod50\xequiv32pmod51.endarrayright.$$The numbers $50$ and $51$ are coprime and $1=51-50$. Therefore,$$-18(=14-32)=-18times51+18times50$$and so$$32-18times51=14-18times51=-866equiv1664pmod!2550.$$So, the answer is $overline1,664$.

share|cite|improve this answer

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is the choice of your initial system arbitrary? So could you also have used $x equiv 14 (mod 51)$ and $x equiv 32(mod 50)$? When I try to solve your system I Get $1664$. Since I would solve: $x=B_1X_1C_1+B_2X_2C_2$ where $B_1=51$, $C_1=14$, $B_2=50$ and $C_2=32$. This then I solve $x=51 cdot 1 cdot 14 - 50 cdot 1 cdot 32 = 1664$. This I would say $x = overline1664$. Do you agree?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:31
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Of course I agree. That's what I got, right?!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah it is, I first saw you got something like $overline932$ but you edited that right when I was typing I guess. Thanks for the help :)
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How did you know you only had to use two out of the four equations from the system? Is that always the case when the 'remainders' are equal in two of the equations?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner Since your comment was posted quite after my edition, I didn't think that you meant the first version of my answer (which had a mistake).
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:59
  

  
  
  
  

 | 
show 3 more comments

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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
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

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3146362%2fusing-chinese-remainder-theorem-for-large-modulo%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

A very simple way: $bmod (50,51)!:, (14,32)equiv 16(color#0a04,color#c002)to 16(color#90f104)=1664 $ since by Easy CRT

$quad beginalignx&equivcolor#0a0 4!!!pmod50\ x&equiv color#c002!!!pmod51endalign$ $iff xequivcolor#c00 2+51underbraceleft[dfraccolor#0a04-color#c00251bmod 50right]_Large equiv 2/1 !equiv color#90f104,pmod50cdot 51$

Remark $ $ Without factoring $, xequiv 51cdotcolor#0a014 - 50cdot color#c0032equiv 714! -! 1600equiv -886equiv 2550-886equiv 1664 $ hence the arithmetic is harder mentally without factoring out $16$ (or $32)$ at the start.

share|cite|improve this answer

edited Mar 14 at 13:37

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) Very nice!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, very nice. Never heard of the Easy CRT before.
  $endgroup$
  – Mathbeginner
  Mar 14 at 9:51
  

  
  
  
  

add a comment | 

2

$begingroup$

A very simple way: $bmod (50,51)!:, (14,32)equiv 16(color#0a04,color#c002)to 16(color#90f104)=1664 $ since by Easy CRT

$quad beginalignx&equivcolor#0a0 4!!!pmod50\ x&equiv color#c002!!!pmod51endalign$ $iff xequivcolor#c00 2+51underbraceleft[dfraccolor#0a04-color#c00251bmod 50right]_Large equiv 2/1 !equiv color#90f104,pmod50cdot 51$

Remark $ $ Without factoring $, xequiv 51cdotcolor#0a014 - 50cdot color#c0032equiv 714! -! 1600equiv -886equiv 2550-886equiv 1664 $ hence the arithmetic is harder mentally without factoring out $16$ (or $32)$ at the start.

share|cite|improve this answer

edited Mar 14 at 13:37

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) Very nice!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, very nice. Never heard of the Easy CRT before.
  $endgroup$
  – Mathbeginner
  Mar 14 at 9:51
  

  
  
  
  

add a comment | 

$begingroup$

A very simple way: $bmod (50,51)!:, (14,32)equiv 16(color#0a04,color#c002)to 16(color#90f104)=1664 $ since by Easy CRT

$quad beginalignx&equivcolor#0a0 4!!!pmod50\ x&equiv color#c002!!!pmod51endalign$ $iff xequivcolor#c00 2+51underbraceleft[dfraccolor#0a04-color#c00251bmod 50right]_Large equiv 2/1 !equiv color#90f104,pmod50cdot 51$

Remark $ $ Without factoring $, xequiv 51cdotcolor#0a014 - 50cdot color#c0032equiv 714! -! 1600equiv -886equiv 2550-886equiv 1664 $ hence the arithmetic is harder mentally without factoring out $16$ (or $32)$ at the start.

share|cite|improve this answer

edited Mar 14 at 13:37

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

share|cite|improve this answer

edited Mar 14 at 13:37

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

answered Mar 13 at 18:42

Bill DubuqueBill Dubuque

212k29195654

2

$begingroup$

All you need to do is to solve the system$$left{beginarraylxequiv14pmod50\xequiv32pmod51.endarrayright.$$The numbers $50$ and $51$ are coprime and $1=51-50$. Therefore,$$-18(=14-32)=-18times51+18times50$$and so$$32-18times51=14-18times51=-866equiv1664pmod!2550.$$So, the answer is $overline1,664$.

share|cite|improve this answer

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is the choice of your initial system arbitrary? So could you also have used $x equiv 14 (mod 51)$ and $x equiv 32(mod 50)$? When I try to solve your system I Get $1664$. Since I would solve: $x=B_1X_1C_1+B_2X_2C_2$ where $B_1=51$, $C_1=14$, $B_2=50$ and $C_2=32$. This then I solve $x=51 cdot 1 cdot 14 - 50 cdot 1 cdot 32 = 1664$. This I would say $x = overline1664$. Do you agree?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:31
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Of course I agree. That's what I got, right?!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah it is, I first saw you got something like $overline932$ but you edited that right when I was typing I guess. Thanks for the help :)
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How did you know you only had to use two out of the four equations from the system? Is that always the case when the 'remainders' are equal in two of the equations?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner Since your comment was posted quite after my edition, I didn't think that you meant the first version of my answer (which had a mistake).
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:59
  

  
  
  
  

 | 
show 3 more comments

2

$begingroup$

All you need to do is to solve the system$$left{beginarraylxequiv14pmod50\xequiv32pmod51.endarrayright.$$The numbers $50$ and $51$ are coprime and $1=51-50$. Therefore,$$-18(=14-32)=-18times51+18times50$$and so$$32-18times51=14-18times51=-866equiv1664pmod!2550.$$So, the answer is $overline1,664$.

share|cite|improve this answer

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is the choice of your initial system arbitrary? So could you also have used $x equiv 14 (mod 51)$ and $x equiv 32(mod 50)$? When I try to solve your system I Get $1664$. Since I would solve: $x=B_1X_1C_1+B_2X_2C_2$ where $B_1=51$, $C_1=14$, $B_2=50$ and $C_2=32$. This then I solve $x=51 cdot 1 cdot 14 - 50 cdot 1 cdot 32 = 1664$. This I would say $x = overline1664$. Do you agree?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:31
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Of course I agree. That's what I got, right?!
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah it is, I first saw you got something like $overline932$ but you edited that right when I was typing I guess. Thanks for the help :)
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How did you know you only had to use two out of the four equations from the system? Is that always the case when the 'remainders' are equal in two of the equations?
  $endgroup$
  – Mathbeginner
  Mar 13 at 10:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner Since your comment was posted quite after my edition, I didn't think that you meant the first version of my answer (which had a mistake).
  $endgroup$
  – José Carlos Santos
  Mar 13 at 10:59
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

All you need to do is to solve the system$$left{beginarraylxequiv14pmod50\xequiv32pmod51.endarrayright.$$The numbers $50$ and $51$ are coprime and $1=51-50$. Therefore,$$-18(=14-32)=-18times51+18times50$$and so$$32-18times51=14-18times51=-866equiv1664pmod!2550.$$So, the answer is $overline1,664$.

share|cite|improve this answer

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

$endgroup$

share|cite|improve this answer

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

edited Mar 13 at 23:33

Bill Dubuque

212k29195654

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236

answered Mar 13 at 10:13

José Carlos SantosJosé Carlos Santos

168k23132236