remainder theorem

This topic has expert replies
Source: — Problem Solving |

Junior | Next Rank: 30 Posts
Posts: 27
Joined: Sun Apr 08, 2012 5:38 am
Thanked: 20 times

by shubham_k » Wed Apr 11, 2012 9:54 am
The problem is to ask
43^43 + 33^33 mod 10

Modular Exponentiation
X^a (mod n).

43^43 mod 10
First,
43^1 mod 10 = 3
43^2 mod 10 = 3^2 mod 10 = 9
43^4 mod 10 = 9^2 mod 10 = 1
43^8 mod 10 = 1^2 mod 10 = 1
....
43^32 mod 10 = 1 mod 10 = 1

43 = 32 + 8 + 2 + 1
43^43 mod 10
= 43^32 mod 10 * 43^8 mod 10 * 43^2 mod 10 + 43^1 mod 10
= (1 * 1 * 9 * 3 ) mod 10
= 27 mod 10
= 7

Same procedure is done on 33
33^1 mod 10 = 3
33^2 mod 10 = 3^2 mod 10 = 9
33^4 mod 10 = 9^2 mod 10 = 1
.....
33^32 mod 10 = 1 mod 10 = 1

33 = 32 + 1
33^33 mod 10
=33^32 mod 10 * 33^1 mod 10
= (1 * 3 ) mod 10
= 3 mod 10
= 3

Therefore, their sum must be 3 + 7 which gives the unit digit 0.
The remainder is obviously 0.

User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Wed Apr 11, 2012 1:18 pm
vaswani.sharan wrote:What is the remainder when 43^43+ 33^33 is divided by 10?
When a positive integer is divided by ten, the remainder is the UNITS DIGIT of the integer.
To illustrate:
25/10 = 2 R5.
Thus, we need to determine the units digit of 43�³ + 33³³.

We can treat this as a PATTERN question.
The strategy: WRITE IT OUT until you see the pattern.

3¹ = 3.
3² = 9.
3³ = 27.
3� = 81.
3� = 243.
Etc.

The units digits repeat in a CYCLE OF 4: 3,9,7,1...3,9,7,1...
Thus, when a positive integer with a units digit of 3 is raised to a power that is a multiple of 4 -- as in 43� -- the units digit will be 1.
From there, the pattern will repeat: 3,9,7,1...3,9,7,1...

Units digit of 43�³:
43�� has a unit digit of 1, since the exponent is a multiple of 4.
From here, the cycle repeats:
43�¹ has a units digit of 3.
43�² has a units digit of 9.
43�³ has a units digit of 7.

Units digit of 33³³:
33³² has a unit digit of 1, since the exponent is a multiple of 4.
From here, the cycle repeats:
33³³ has a units digit of 3.

Since 43�³ has a units digit of 7, 33³³ has a units digit of 3, and 7+3 = 10, the units digit of 43�³ + 33³³ is 0.
Thus, the remainder when 43�³ + 33³³ is divided by 10 will be 0.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3

Master | Next Rank: 500 Posts
Posts: 110
Joined: Wed Feb 22, 2012 11:28 pm
Location: India
Thanked: 13 times
Followed by:1 members

by spartacus1412 » Thu Apr 12, 2012 12:08 am
43^43 +33^33 mod 10 intends to find the units digit of 43^43+33^33
You would have noticed that the exponent powere start repeating their units digit at an interval of 4
Eg.consider the units digit in
3^1 it is 3
3^2 it is 9
3^3 it is 7
3^4 it is 1
3^5 it is 3
3^2 it is 9
3^3 it is 7
3^4 it is 1
...
so you can see units digit repeat at an interval of four

hence, 3^5 has the same units digit as 3^1 or 3^9

In this case, 43^43 will have the same units digit as 43^3, more clearly the units digits will be 3^3. (43 = 4*10 +3, hence , 3 is the modulous for power)
similarly for 34^34 the units digit will be same as 33^2, more clearly the units digits will be 3^1.
(33 = 4*8 +2, hence , 2 is the modulous for power)

hence add, 3^3 + 3^1 to get the units digit ==adding units digit(7 +3)= 10

Hope this helps!
Its do or die this time!
Practise, practise and practise.