Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need some help with this problem:

$$439^{233} \mod 713$$

I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this.

Thanks.

share|improve this question
4  

5 Answers 5

up vote 8 down vote accepted

There are often tricks to this if the numbers are nice enough, but even if they're not, here's a way that's not entirely horrible.

You already know what 439 is mod 713. What is $439^2 \mod 713$? What about $439^4$? (Hint: take your answer for $439^2$ after reducing it mod 713, and then square it again.) In the same way, calculate $439^8, 439^{16}, \dots, 439^{128} \mod 713$. Now just note that 233 = 128 + 64 + 32 + 8 + 1. So multiply the appropriate powers of 439 together - again, one calculation at a time, reducing mod 713 each time.

Now you should only have to do 11 calculations, and now all your numbers are 6 digits or less. Rather than impossible, it's now simply tedious. :)

By the way, one thing to notice: 713 = 23 * 31. Perhaps your calculations will be easier if you do them mod 23 and 31, then apply the Chinese remainder theorem?

share|improve this answer

You can do this step by step by first computing $439^2\equiv 211 {\ \rm mod\ }713$. Then you compute $439^4\equiv 211^2 \equiv 315 {\ \rm mod\ }713$. Continue to square and reduce mod $713$ and build up a list of powers $$439^1, \qquad 439^2, \qquad 439^4 \qquad \dots \qquad 439^{128}\qquad \qquad ({\rm mod\ }713)$$ Finally, write $233$ as a sum of powers of $2$, and compute $$439^{233}=439^{1+8+32+64+128}=439\cdot 439^8\cdot 439^{32}\cdot439^{64}\cdot 439^{128} \qquad ({\rm mod\ }713)$$ Just remember to reduce mod $713$ each time you get a product which is larger than $713$.

share|improve this answer

You can go fast if you incrementally square: $439^2=211 \pmod{713}$; $211^2=315 \pmod{713}$; $315^2=118 \pmod{713}$; $315^2=377 \pmod{713}$; $377^2=242 \pmod{713}$; $377^2=98 \pmod{713}$; etc.

The last one means $439^{64}=98 \pmod{713}$; In this way you can combine and reach 233 fast.

Ultimately $439^{233}=211 \pmod{713}$;

share|improve this answer

$713=23\cdot 31$

$439 \pmod {23}=2$ and $\phi(23)=22$ and $233\equiv 13{\pmod {22}}$

So, $439^{223} {\pmod {23}} \equiv 2^{22\cdot 10 + 13}\equiv {(2^{22})}^{10}2^{13}\equiv 2^{13} {\pmod {23}}$ using Euler's Totient Theorem.

$2^6\equiv 18 {\pmod {23}}, 2^7\equiv 36 \equiv 13$

$\implies 2^{13}\equiv 18\cdot 13=234\equiv 4 {\pmod {23}}=4+23x$ for some integer $x$.

$439 \pmod {31}=5$ and $\phi(31)=30$ and $233\equiv 23{\pmod {30}}$

So, $439^{223} {\pmod {31}} \equiv 5^{23} {\pmod {31}}$

$5^3 \equiv 1 {\pmod {31}} \implies 5^{23}\equiv({5^3})^7 5^2\equiv 5^2{\pmod {31}}=25+31y$ for some integer $y$.

So, we need to find $z$ such that $z=25+31y=4+23x$

Expressing as continued fraction, $$\frac{31}{23}=1+\frac{8}{23}=1+\frac{1}{\frac{23}{8}}=1+\frac{1}{2+\frac{7}{8}}$$

$$=1+\frac{1}{2+\frac{1}{\frac{8}{7}}}=1+\frac{1}{2+\frac{1}{1+\frac{1}{7}}}$$

So, the last but one convergent is $$1+\frac{1}{2+\frac{1}{1}}=\frac{4}{3}$$

So, $23\cdot 4- 31\cdot 3=-1$

$25+31y=4+23x\implies 23x=31y+21(31\cdot 3-23\cdot 4)$ $\implies 23(x+84)=31(y+63)$ $$\implies x+84=\frac{31(y+63)}{23}$$

So, $23\mid (y+63)$ as $x+84$ is integer and $(31,23)=1$ i.e., $ 23\mid (y+69-6)\implies 23\mid (y-6) \implies y=6+23w$

So, $z=25+31y=25+31(6+31w)=713w+211 \equiv 211 {\pmod {713}}$

share|improve this answer
    
Thank you for your answer! I'll ask a friend of mine to explain this to me, I'm fairly new to modulus calculation haha. –  Gideon Potgieter Sep 14 '12 at 10:03

Here`s the algorithm,basically it is Modular exponentiation.

function modular_pow(base, exponent, modulus)

result := 1

while exponent > 0
    if (exponent mod 2 == 1):
       result := (result * base) mod modulus
    exponent := exponent >> 1
    base = (base * base) mod modulus
return result

Also here is the working code in c++ which can work for upto 10^4 test cases,in 0.7 seconds Also the ideone link http://ideone.com/eyLiOP

#include <iostream>
using namespace std;
#define mod 1000000007


long long int modfun(long long int a,long long int b)
{
     long long int result = 1;
    while (b > 0)
       {
           if (b & 1)
           {
               a=a%mod;
               result = (result * a)%mod;
               result=result%mod;
           }
        b=b>>1;
        a=a%mod;
        a = (a*a)%mod;
        a=a%mod;
       }
    return result;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        {
           long long int a,b;
           cin>>a>>b;
           if(a==0)
            cout<<0<<"\n";
           else if(b==0)
            cout<<1<<"\n";
           else if(b==1)
            cout<<a%mod<<"\n";
           else
           {
               cout<<(modfun(a,b))%mod<<"\n";
           }

        }
    return 0;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.