If n^m leaves a remainder of 1 after division by 7 for all

Hello BTGmoderatorLU.

I would solve it as follows.

Since the statement must be true for all values of n that are not multiples of 7, then I picked n=3.

Now, let's try the values of m.

If m=2 then 3^2 = 9, remainder 2. Out.

If m=3 then 3^3 = 27, remainder 6. Out.

If m=4 then 3^4 = 81, remainder 4. Out.

If m=5 then 3^5 = 243, remainder 5. Out.

If m=6 then 3^6 = 729, remainder 1. Correct.

So, the correct answer is the option E.

I hope it helps you. <i class="em em-smiley"></i>

BTGmoderatorLU wrote:If n^m leaves a remainder of 1 after division by 7 for all positive integers n that are not multiples of 7, then m could be equal to:

A. 2
B. 3
C. 4
D. 5
E. 6

Let’s test each answer choice.

A. m = 2

If n = 2, we see that 2^2/7 = 4/7 = 0 R 4, so m could not be 2.

B. m = 3

If n = 3, we see that 3^3/7 = 27/7 = 3 R 6, so m could not be 3.

C. m = 4

If n = 2, we see that 2^4/7 = 16/7 = 2 R 2, so m could not be 4.

D. m = 5

If n = 2, we see that 2^5/7 = 32/7 = 4 R 4, so m could not be 5.

At this point, we see that the correct choice must be E, but let’s verify that is case anyway.

E. m = 6

If n = 1, we see that 1^6/7 = 1/7 = 0 R 1.
If n = 2, we see that 2^6/7 = 64/7 = 9 R 1.
If n = 3, we see that 3^6/7 = 729/7 = 104 R 1.

We can stop at this point before the numbers get too large; we can see that E is the correct answer choice.

Answer: E

Fermat little theorem is the best way to solve it.
We can also do it using Euler's function as well
7*(1-1/7)= 6

________________________________________

Shahrukh Moin Khan
QA Mentor at Breakspace
https://www.mbabreakspace.com
PGDM: IIM Calcutta
B.Tech IIT Roorkee