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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$.

Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number?

We have a finite range in which both $a$ and $b$ belong so we can just check for all values of $a$ and $b$ that satisfy the given gcd and get the maximum value of $a^b \bmod N$.

But I do feel there might be a better approach to approach this problem.So please guide me.

Also is there a way around this problem if we only know $\gcd(a,b) \bmod N$ for $a$ and $b$ instead of $\gcd(a,b).

Can we still come up with something to determine the maximum value of $a^b \bmod N$.

share|cite|improve this question
The question is unclear. I think you mean that $A$ and $B$ are unknown positive integers in some known range; $d=\gcd(A,B)$ is known; (A^B)%n means $A^B$ reduced modulo $n$ to lie between zero and $n-1$, inclusive; $n$ is given; you want to choose $A,B$ to maximize $A^B\mod n$, preferably without trying every $A,B$. If that's what you mean, please edit your question accordingly. I don't know what you mean by "we only know the gcd%$n$ for such a set of numbers." What does "such a set of numbers" mean? – Gerry Myerson Jun 11 '12 at 7:13
Yes please clarify the notation in the question. Conceivably A^B denotes the gcd of $A$ and $B$ rather than $A$ to the power $B$, which would maybe make a bit more sense, but in any case change the question entirely. Knowing the gcd of $A$ and $B$ is not of much help really if you are actually interested in $A$ to the power $B$. – Marc van Leeuwen Jun 11 '12 at 7:24
By set of numbers I mean A and B only,and yes it is A raised to the power B. I have modified the question accordingly.Thanks. – Abhisar Singhal Jun 11 '12 at 9:50
Thanks for clearing things up. I doubt there's any way to do what you want. To begin with, the concept of maximizing a modular value is unnatural, e.g., if you add 1 to 16 you get something bigger, but if you add 1 to 16 mod 17, you get something "smaller", namely, zero. But I hope someone proves me wrong. – Gerry Myerson Jun 11 '12 at 12:56

Your Answer


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

Browse other questions tagged or ask your own question.