# Determining maximum value of $a^b\bmod N$ when $\gcd(a,b)$ is known

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$. - 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