BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

og12

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Senior | Next Rank: 100 Posts
Posts: 50
Joined: Fri Jan 28, 2011 1:08 pm

og12

by gmatapril » Fri Jan 28, 2011 1:16 pm
If n is a prime number greater than 3, what is the
remainder when n^2 is divided by 12 ?
Answer is 1

According to OG explanation
For the more mathematically inclined, consider
the remainder when each prime number n greater
than 3 is divided by 6. Th e remainder cannot be 0
because that would imply that n is divisible by 6,
which is impossible since n is a prime number.
Th e remainder cannot be 2 or 4 because that
would imply that n is even, which is impossible
since n is a prime number greater than 3. Th e
remainder cannot be 3 because that would imply
that n is divisible by 3, which is impossible since
n is a prime number greater than 3. Th erefore,
the only possible remainders when a prime
number n greater than 3 is divided by 6 are 1
and 5. Th us, n has the form 6q + 1 or 6q + 5,
where q is an integer, and, therefore, n2 has the
form 36q2 + 12q + 1 = 12(3q2 + q) + 1 or
36q2 + 60q + 25 = 12(3q2 + 5q + 2) + 1. In either
case, n^2 has a remainder of 1 when divided by 12.



my doubts are
1. why they have used no. 6 to divide by n why not 12
2.why the remainder cannot be 2 or 4 how did we know that n will be even then.

please clear my doubts
Top
Source: — Problem Solving |

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3835
Joined: Fri Apr 02, 2010 10:00 pm
Location: Milpitas, CA
Thanked: 1854 times
Followed by:523 members
GMAT Score:770

by Anurag@Gurome » Fri Jan 28, 2011 2:25 pm
gmatapril wrote:If n is a prime number greater than 3, what is the
remainder when n^2 is divided by 12 ?

....

my doubts are
1. why they have used no. 6 to divide by n why not 12
2.why the remainder cannot be 2 or 4 how did we know that n will be even then.
This problem can be easily solved if you know a property of any prime number greater than 3. In fact, the solution also uses the fact, but indirectly. The property is : Any prime number greater than 3 can be expressed as either (6a + 1) or (6a - 1), where a is a positive integer. There is a simple logic behind this. Let me explain why...

When any positive integer is divided by 6, the possible remainders are 0, 1, 2, 3, 4, and 5. Hence any positive integer can be written as any one of the following: 6a, (6a + 1), (6a + 2), (6a + 3), (6a + 4), and (6a + 5), where a is a non-negative integer. Now, out of these, 6a, (6a + 2), (6a + 3), and (6a + 4) can't be a prime greater than 3 as they are either divisible by 2 or 3 or both. Hence, only (6a + 1) and (6a + 5) can be prime. Now, (6a + 5) is same as (6a - 1) in terms of divisibility by 6.

Thus any prime greater than 3 can expressed as either (6a + 1) or (6a - 1), where a is a positive integer. Please note that this doesn't mean any integer of this form will be a prime.


Now, if n is prime number greater than 3, then we can write n as (6a ± 1)
Hence, n² = (6a ± 1)² = (36a² ±12a + 1) = 12(3a² ±a) + 1

Hence, the remainder when n² is divided by 12 is 1.
Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3835
Joined: Fri Apr 02, 2010 10:00 pm
Location: Milpitas, CA
Thanked: 1854 times
Followed by:523 members
GMAT Score:770

by Anurag@Gurome » Fri Jan 28, 2011 2:37 pm
gmatapril wrote:If n is a prime number greater than 3, what is the remainder when n^2 is divided by 12 ?
The best approach to solve this problem is to pick a prime number greater than 3 and check for the remainder when divided by 12.

Let's say, n = 5
Then, n² = 25

When 25 is divided by 12, the remainder is 1.
Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/
Top
Senior | Next Rank: 100 Posts
Posts: 35
Joined: Mon Jan 03, 2011 4:56 pm
Location: Calif
Thanked: 2 times
Followed by:1 members

by Everest » Fri Jan 28, 2011 2:58 pm
If n is a prime number greater than 3, what is the
remainder when n^2 is divided by 12 ?


Easy method is substitution of primes greater than 3.

5 is a prime number greater than 3

5^2 = 25 , when 25 is divided by 12 remainder is 1.
Top
Senior | Next Rank: 100 Posts
Posts: 50
Joined: Fri Jan 28, 2011 1:08 pm

by gmatapril » Fri Jan 28, 2011 2:59 pm
Anurag@Gurome wrote:
gmatapril wrote:If n is a prime number greater than 3, what is the
remainder when n^2 is divided by 12 ?

....

my doubts are
1. why they have used no. 6 to divide by n why not 12
2.why the remainder cannot be 2 or 4 how did we know that n will be even then.
This problem can be easily solved if you know a property of any prime number greater than 3. In fact, the solution also uses the fact, but indirectly. The property is : Any prime number greater than 3 can be expressed as either (6a + 1) or (6a - 1), where a is a positive integer. There is a simple logic behind this. Let me explain why...
if we were asked any prime number greater than 7 how will we express it in terms of a
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3835
Joined: Fri Apr 02, 2010 10:00 pm
Location: Milpitas, CA
Thanked: 1854 times
Followed by:523 members
GMAT Score:770

by Anurag@Gurome » Fri Jan 28, 2011 3:05 pm
gmatapril wrote:if we were asked any prime number greater than 7 how will we express it in terms of a
If we can represent any prime number greater than 3 as (6a + 1) or (6a - 1), we can represent any prime number greater than 7 also in the same way. That's because any prime number greater than 7 is also greater than 3.

Note that there is no unique way to represent prime numbers. Prime numbers can be represented in different manner. Depending upon the problem, we have to select the most convenient method of representation.

Go for picking number approach.
There is no need for this kind of representations of prime numbers for GMAT.
Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/
Top
Senior | Next Rank: 100 Posts
Posts: 93
Joined: Fri Feb 19, 2010 11:52 am
Thanked: 1 times

by Reva » Fri Jan 28, 2011 5:56 pm
Thank you. Even I find that method easier its little hard to remember such rules
Top
Junior | Next Rank: 30 Posts
Posts: 16
Joined: Fri Jan 28, 2011 12:36 am
Thanked: 1 times

by diehard_gmat » Sat Jan 29, 2011 3:31 am
Thanks a ton Anurag!
There is so much to learn from you!
Top
User avatar
GMAT Instructor
Posts: 1462
Joined: Thu Apr 09, 2015 9:34 am
Location: New York, NY
Thanked: 39 times
Followed by:22 members

by Jeff@TargetTestPrep » Sun Apr 19, 2015 6:22 am
gmatapril wrote:If n is a prime number greater than 3, what is the
remainder when n^2 is divided by 12 ?
Answer is 1

According to OG explanation
For the more mathematically inclined, consider
the remainder when each prime number n greater
than 3 is divided by 6. Th e remainder cannot be 0
because that would imply that n is divisible by 6,
which is impossible since n is a prime number.
Th e remainder cannot be 2 or 4 because that
would imply that n is even, which is impossible
since n is a prime number greater than 3. Th e
remainder cannot be 3 because that would imply
that n is divisible by 3, which is impossible since
n is a prime number greater than 3. Th erefore,
the only possible remainders when a prime
number n greater than 3 is divided by 6 are 1
and 5. Th us, n has the form 6q + 1 or 6q + 5,
where q is an integer, and, therefore, n2 has the
form 36q2 + 12q + 1 = 12(3q2 + q) + 1 or
36q2 + 60q + 25 = 12(3q2 + 5q + 2) + 1. In either
case, n^2 has a remainder of 1 when divided by 12.



my doubts are
1. why they have used no. 6 to divide by n why not 12
2.why the remainder cannot be 2 or 4 how did we know that n will be even then.

please clear my doubts
If n is a prime number greater than 3, what is the remainder when n^2 is divided by 12?

A. 0
B. 1
C. 2
D. 3
E. 5

Solution:

We see that n can be ANY PRIME NUMBER GREATER THAN 3. Let's choose the smallest prime number greater than 3 and substitute it for n; that number is 5.

We know that 5 squared is 25, so we now divide 25 by 12:

25/12 = 2, Remainder 1.

If you are not convinced by trying just one prime number, try another one. Let's try 7. We know that 7 squared equals 49, so we now divide 49 by 12:

49/12 = 4, Remainder 1.

It turns out that in this problem it doesn't matter which prime number (greater than 3) we choose. The remainder will always be 1 when its square is divided by 12.

The answer is B

Jeffrey Miller
Head of GMAT Instruction
[email protected]

Image

See why Target Test Prep is rated 5 out of 5 stars on BEAT the GMAT. Read our reviews
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Sun Apr 19, 2015 11:05 pm
Anurag's solution seems to me to draw on much higher math than is required, so let's do this another way.

Given any three consecutive integers, ONE of them must be divisible by 3. Let's take the three consecutive integers

(n - 1), n, (n + 1)

Since n is prime > 3, we know that either (n - 1) or (n + 1) is divisible by 3.

Further, since n is odd, both (n - 1) and (n + 1) are even.

That means that (n - 1) * (n + 1) must contain TWO factors of 2 (one from each even number) and ONE factor of 3. That gives us 2 * 2 * 3 = 12.

(n - 1) * (n + 1) = n² - 1, so (n² - 1) is a multiple of 12. That means that n² = (multiple of 12) + 1, so n² always has a remainder of 1 when divided by 12.

In fact, if n is a prime greater than 3, we can go even further than this, and say that n² always has a remainder of 1 when divided by 24 ... but I'll leave that proof for the curious. ^_^
Top
Post new topic Post Reply
• Page 1 of 1