3
$\begingroup$

Given that $719$ is prime, find the least positive residue of $11^{721} \pmod {719}$, without using modular exponentiation.

So, I know how to use modular exponentiation and have done it to get the answer $612$, but I have no idea how to do this without modular exponentiation...

Any ideas for a method I can try?

$\endgroup$

2 Answers 2

9
$\begingroup$

HINT:

As $719$ is prime, $(11,719)=1$ and $11^{719-1}\equiv1\pmod {719}$ using Fermat's Little Theorem

So, $11^{721}=11^3\cdot11^{718}\equiv 11^3\pmod{719}\equiv\cdots$

$\endgroup$
1
  • $\begingroup$ Ah thank you ! so simple ... Will accept in 10 min when I can $\endgroup$
    – Rawb
    Sep 12, 2013 at 18:12
-1
$\begingroup$

This is a simple application of Fermat's Little theorem.

** if M is prime, then to find ab % M,

r = b % (M-1)

c = a % M

ab % M = cr % M

**

721 % 718 = 3

11 % 719 = 11

Therefore, 11721 % 719 = 113 % 719 = 612

So, there is no need to perform modular exponentiation if Mod value is given prime.

$\endgroup$
2
  • $\begingroup$ This is quite difficult to read, in large part due to the lack of proper formatting. Can you please go over the MathJax guide, and edit your answer for readability? It should also be noted that the use of % for modular division is relatively uncommon in mathematical notation. If you are going to use that notation, it would be helpful if you took a couple of words to explain what, exactly, it means (for example, my recollection is that the C programming language uses % in a way that is distinct from the usual notation in mathematics). $\endgroup$
    – Xander Henderson
    Mar 31, 2019 at 17:48
  • $\begingroup$ @XanderHenderson sir, first of all I'm sorry for my failure by not being able to make my solution readable to you. Actually this is relative issue, I agree. For being a student of computer science background, I have got familiar with irrelevant notation instead of proper mathematical notation. I will study more on it. $\endgroup$ Mar 31, 2019 at 23:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .