What is the approach for solving these kinds of modular arithmetic? [duplicate]

This question already has an answer here:

How do I compute $a^b,bmod c$ by hand?

9 answers

I am new to modular arithmetic. I have gone through a few formulae related to this but I am unable to solve problems like (5^12) mod 23. I am not really bothered about the final answer, but mainly on the approach on these kinds of problems (or maybe more involving complex powers). Any help is appreciated. Thank you.

asked Dec 29 '18 at 0:38

Avishek Paul

marked as duplicate by max_zorn, Bill Dubuque, Lord Shark the Unknown, metamorphy, user91500 Dec 29 '18 at 10:25

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

$begingroup$
Please read the following: khanacademy.org/computing/computer-science/cryptography/…
$endgroup$
– Noble Mushtak
Dec 29 '18 at 0:57

$begingroup$
Fermat's little theorem and Euler's totient function come to mind.
$endgroup$
– Mohammad Zuhair Khan
Dec 29 '18 at 0:58

add a comment |

This question already has an answer here:

How do I compute $a^b,bmod c$ by hand?

9 answers

asked Dec 29 '18 at 0:38

Avishek Paul

marked as duplicate by max_zorn, Bill Dubuque, Lord Shark the Unknown, metamorphy, user91500 Dec 29 '18 at 10:25

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

$begingroup$
Please read the following: khanacademy.org/computing/computer-science/cryptography/…
$endgroup$
– Noble Mushtak
Dec 29 '18 at 0:57

$begingroup$
Fermat's little theorem and Euler's totient function come to mind.
$endgroup$
– Mohammad Zuhair Khan
Dec 29 '18 at 0:58

add a comment |

This question already has an answer here:

How do I compute $a^b,bmod c$ by hand?

9 answers

asked Dec 29 '18 at 0:38

Avishek Paul

This question already has an answer here:

How do I compute $a^b,bmod c$ by hand?

9 answers

This question already has an answer here:

How do I compute $a^b,bmod c$ by hand?

9 answers

arithmetic

asked Dec 29 '18 at 0:38

Avishek Paul

asked Dec 29 '18 at 0:38

Avishek Paul

asked Dec 29 '18 at 0:38

Avishek Paul

asked Dec 29 '18 at 0:38

Avishek Paul

asked Dec 29 '18 at 0:38

Avishek Paul

marked as duplicate by max_zorn, Bill Dubuque, Lord Shark the Unknown, metamorphy, user91500 Dec 29 '18 at 10:25

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 max_zorn, Bill Dubuque, Lord Shark the Unknown, metamorphy, user91500 Dec 29 '18 at 10:25

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

$begingroup$
Please read the following: khanacademy.org/computing/computer-science/cryptography/…
$endgroup$
– Noble Mushtak
Dec 29 '18 at 0:57

$begingroup$
Fermat's little theorem and Euler's totient function come to mind.
$endgroup$
– Mohammad Zuhair Khan
Dec 29 '18 at 0:58

add a comment |

1

$begingroup$
Please read the following: khanacademy.org/computing/computer-science/cryptography/…
$endgroup$
– Noble Mushtak
Dec 29 '18 at 0:57

$begingroup$
Fermat's little theorem and Euler's totient function come to mind.
$endgroup$
– Mohammad Zuhair Khan
Dec 29 '18 at 0:58

Please read the following: khanacademy.org/computing/computer-science/cryptography/…

– Noble Mushtak
Dec 29 '18 at 0:57

Fermat's little theorem and Euler's totient function come to mind.

– Mohammad Zuhair Khan
Dec 29 '18 at 0:58

add a comment |

1 Answer
1

active

oldest

votes

Rewriting "big" numbers like $920 ,rm{mod}, 1000$ as "smaller" numbers: $920 equiv -80$.

Finding patterns in exponents (for example, $2^n ,rm{mod}, 10$ has a cycle $2,, 4,, 8,, 6$ with $4$ steps).

Reducing big exponents using Euler's $phi$.

Squaring (!). For example, in $231^{19} ,rm{mod},517$, you might find, first, $231^2$ and then use that $231^{19} = {(231^2)}^9times 231$. Iterating this makes every congruence so, oh so much easier..

Those are the main techniques I'm aware of.

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

add a comment |

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

Rewriting "big" numbers like $920 ,rm{mod}, 1000$ as "smaller" numbers: $920 equiv -80$.

Finding patterns in exponents (for example, $2^n ,rm{mod}, 10$ has a cycle $2,, 4,, 8,, 6$ with $4$ steps).

Reducing big exponents using Euler's $phi$.

Squaring (!). For example, in $231^{19} ,rm{mod},517$, you might find, first, $231^2$ and then use that $231^{19} = {(231^2)}^9times 231$. Iterating this makes every congruence so, oh so much easier..

Those are the main techniques I'm aware of.

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

add a comment |

Rewriting "big" numbers like $920 ,rm{mod}, 1000$ as "smaller" numbers: $920 equiv -80$.

Finding patterns in exponents (for example, $2^n ,rm{mod}, 10$ has a cycle $2,, 4,, 8,, 6$ with $4$ steps).

Reducing big exponents using Euler's $phi$.

Squaring (!). For example, in $231^{19} ,rm{mod},517$, you might find, first, $231^2$ and then use that $231^{19} = {(231^2)}^9times 231$. Iterating this makes every congruence so, oh so much easier..

Those are the main techniques I'm aware of.

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

add a comment |

Rewriting "big" numbers like $920 ,rm{mod}, 1000$ as "smaller" numbers: $920 equiv -80$.

Finding patterns in exponents (for example, $2^n ,rm{mod}, 10$ has a cycle $2,, 4,, 8,, 6$ with $4$ steps).

Reducing big exponents using Euler's $phi$.

Squaring (!). For example, in $231^{19} ,rm{mod},517$, you might find, first, $231^2$ and then use that $231^{19} = {(231^2)}^9times 231$. Iterating this makes every congruence so, oh so much easier..

Those are the main techniques I'm aware of.

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

Rewriting "big" numbers like $920 ,rm{mod}, 1000$ as "smaller" numbers: $920 equiv -80$.

Finding patterns in exponents (for example, $2^n ,rm{mod}, 10$ has a cycle $2,, 4,, 8,, 6$ with $4$ steps).

Reducing big exponents using Euler's $phi$.

Squaring (!). For example, in $231^{19} ,rm{mod},517$, you might find, first, $231^2$ and then use that $231^{19} = {(231^2)}^9times 231$. Iterating this makes every congruence so, oh so much easier..

Those are the main techniques I'm aware of.

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

edited Dec 29 '18 at 1:18

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

answered Dec 29 '18 at 1:06

Lucas Henrique

1,031414

add a comment |

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

搜尋此網誌

Ytukyg