- WELCOME TO A LESSON ON MODULAR ARITHMETIC.
IN THIS LESSON, WE'LL PERFORM MODULAR ARITHMETIC BY HAND
ON THE CALCULATOR
AND ALSO VERIFY MODULAR EXPONENT RULES.
IF YOU THINK BACK TO PERFORMING DIVISION WITH WHOLE NUMBERS,
YOU MAY REMEMBER FINDING THE WHOLE NUMBER RESULT
IN THE REMAINDER AFTER DIVISION.
WELL, THE MODULUS IS ANOTHER NAME
FOR THE REMAINDER AFTER DIVISION.
FOR EXAMPLE, 17 MOD 5 = 2 SINCE IF WE DIVIDE 17 BY 5,
WE GET 3 WITH A REMAINDER OF 2.
SOMETIMES INSTEAD OF SEEING 17 MOD 5 = 2,
YOU'LL SEE IT WRITTEN LIKE THIS,
WHERE WE SAY 17 IS CONGRUENT TO 2 MOD 5
WHICH MEANS 17 AND 2 ARE EQUIVALENT
AFTER YOU CONSIDER THE MODULUS 5.
LET'S TAKE A LOOK AT SOME EXAMPLES.
WE WANT TO COMPUTE THE FOLLOWING.
SO FOR 15 MOD 6,
WE WANT TO FIND THE REMAINDER WHEN DIVIDING 15 BY 6.
SO 15 DIVIDED BY 6, THERE ARE 2 6s IN 15.
2 x 6 = 12, WE SUBTRACT.
NOTICE HERE THE REMAINDER IS 3 AND THEREFORE 15 MOD 6 = 3.
NEXT, WE HAVE 35 MOD 7,
SO WE WANT TO FIND THE REMAINDER WHEN WE DIVIDE 35 BY 7.
NOTICE IN THIS CASE, 7 DIVIDES EVENLY INTO 35 SINCE 5 x 7 = 35,
AND SINCE THE REMAINDER WOULD BE 0, 35 MOD 7 = 0.
NEXT, WE HAVE 3 TO THE 4th MOD 4.
3 TO THE 4th IS EQUAL TO 3 x 3 x 3 x 3 OR 81,
SO THIS IS EQUIVALENT TO 81 MOD 4.
SO WE'LL FIND THE REMAINDER WHEN DIVIDING 81 BY 4.
WELL, WE SHOULD RECOGNIZE THERE ARE 20 4s IN 81
SINCE 20 x 4 IS 80 LEAVING US WITH A REMAINDER OF 1,
AND THEREFORE 3 TO THE 4th MOD 4 = 1.
BEFORE WE TALK ABOUT HOW TO DO THIS ON CALCULATOR,
REMEMBER WHEN WE PERFORM THIS DIVISION HERE,
WE COULD ALSO WRITE THE QUOTIENTS AS 2,
AND THEN WE CAN ALSO PUT THE REMAINDER OVER THE DIVISOR
AND WRITE THIS AS 2 3/6 OR IN THIS CASE 2 1/2.
AND FOR OUR LAST EXAMPLE, WE COULD WRITE THIS AS 20 1/4,
THE REMAINDER OVER THE DIVISOR.
SO AGAIN, RECALL THAT WHEN WE DIVIDE 17 BY 5,
WE COULD REPRESENT THE RESULT AS 3, REMAINDER 2,
AS THE MIXED NUMBER 3 2/5, OR AS A DECIMAL 3.4.
NOTICE THAT THE MODULUS 2 IS THE SAME AS THE NUMERATOR
OF THE FRACTIONAL PART OF THE MIXED NUMBER
AND THAT THE DECIMAL PART, 0.4, IS EQUIVALENT TO THAT FRACTION.
WE CAN USE THESE CONVERSATIONS TO CALCULATE THE MODULUS
ON A STANDARD CALCULATOR.
SO FOR "A" MOD N ON A CALCULATOR, WE DIVIDE "A" BY N,
SUBTRACT THE WHOLE NUMBER OR PART OF THE RESULTING QUANTITY,
THEN MULTIPLY BY N TO OBTAIN THE MODULUS.
SO LET'S TRY A COUPLE OF THESE.
HERE WE HAVE 18,396 MOD 5.
WHEN DIVIDING BY 5, WE SHOULD BE ABLE TO DETERMINE THE REMAINDER
JUST BY LOOKING AT THE LAST DIGIT OF THIS NUMBER.
LET'S GO AHEAD AND SHOW IT ANYWAY ON THE CALCULATOR.
WE WOULD TAKE 18,396, DIVIDE BY 5, ENTER,
SUBTRACT THE WHOLE NUMBER PART SO SUBTRACT 3,679, ENTER,
AND THEN x 5.
SO THE REMAINDER WOULD BE 1, AND THEREFORE THIS IS EQUAL TO 1.
NEXT, 362,125 MOD 862, SO WE'LL TAKE 362, 125 DIVIDE BY 862,
ENTER, SUBTRACT THE WHOLE NUMBER OF 420, ENTER,
AND MULTIPLY BY 862.
SO 85 WOULD BE THE REMAINDER WHEN PERFORMING THIS DIVISION,
AND THEREFORE THIS EQUAL TO 85.
NOW, LET'S TALK ABOUT MODULAR EXPONENT RULES.
FIRST WE HAVE "A" RAISED TO THE POWER OF B MOD N = "A" MOD N
RAISED TO THE POWER OF B MOD N.
LET'S VERIFY THIS USING 7 TO THE 8th MOD 5.
SO WE'LL FIRST DETERMINE 7 TO THE 8th MOD 5.
AND THEN APPLYING THE EXPONENT RULE,
WE SHOULD GET THE SAME RESULT
IF WE HAVE 7 MOD 5 RAISED TO THE 8th MOD 5.
SO LET'S FIRST FIND 7 TO THE 8th.
SO WE HAVE 5,764,801 AND NOW WE'LL DIVIDE BY 5,
BUT WE SHOULD RECOGNIZE THAT THE REMAINDER IS GOING TO BE 1
BY LOOKING AT THE LAST DIGIT OF THIS NUMBER.
WE'LL GO AHEAD AND TAKE THIS AND DIVIDE BY 5,
SUBTRACT THE WHOLE NUMBER PART, THEN MULTIPLY BY 5
WHICH DOES GIVE US 1
WHICH MEANS WE SHOULD GET THE SAME RESULT IN THIS FORM HERE.
WELL, 7 MOD 5 WOULD BE 2, SINCE IF WE DIVIDE 7 BY 5,
THE REMAINDER WOULD BE 2.
SO THIS WOULD BE EQUAL TO 2 RAISED TO THE POWER OF 8 MOD 5.
2 TO THE 8th = 256.
256 MOD 5, AGAIN WE SHOULD BE ABLE TO RECOGNIZE
THIS WOULD BE EQUAL TO 1,
PLUS VERIFY IT ON THE CALCULATOR.
SO WE HAVE 256 DIVIDED BY 5, ENTER,
MINUS THE WHOLE NUMBER OF 51, ENTER,
x 5 WHICH ALSO GIVES US 1.
SO THIS DOES VERIFY OUR EXPONENT RULE.
LET'S TAKE A LOOK AT ONE MORE EXPONENT RULE.
YOU MAY REMEMBER FROM ALGEBRA
THAT "A" RAISED TO THE POWER OF B, RAISED TO THE POWER OF C
IS EQUAL TO "A" RAISED TO THE POWER OF B x C.
SO IF WE POWERS RAISED TO POWERS,
WE MULTIPLY THE EXPONENTS,
AND THE ORDER OF MULTIPLICATION CAN BE CHANGED.
WE COULD COMBINE THE MODULAR EXPONENT RULE
WITH THIS EXPONENT RULE
TO DEFINE THE MODULAR EXPONENT POWER RULE STATED HERE.
LET'S LOOK AT THE MIDDLE FIRST.
THIS TELLS US THAT "A" RAISED TO THE POWER OF B x C MOD N
IS EQUAL TO "A" RAISED TO THE POWER OF B MOD N
RAISED TO THE POWER OF C MOD N
WHICH IS ALSO EQUAL TO "A" RAISED TO THE POWER OF C MOD N,
RAISED TO THE POWER OF B MOD N.
LET'S FINISH BY VERIFYING THIS EXPONENT RULE.
SO WE'LL START IN THE MIDDLE, FIND THE RESULTS AND VERIFY
WE GET THE SAME RESULT USING THIS FORM AND THIS FORM.
TO DO THIS, WE'LL CONSIDER 3
RAISED TO THE POWER OF 2 x 4 MOD 7.
TO SAVE SOME TIME, THIS WOULD BE 3 TO THE 8th WHICH = 6,561.
SO LET'S FIND 6,561 MOD 7.
SO WE'LL TAKE 6,561, DIVIDE BY 7, ENTER,
SUBTRACT THE WHOLE NUMBER OF 937, AND THEN x 7.
THIS TELLS US THE REMAINDER WOULD BE 2 WHEN DIVIDING BY 7,
THEREFORE THIS EQUAL TO 2.
NOTICE USING THIS EXAMPLE, "A" IS 3, B IS 2, C IS 4,
AND N IS 7.
SO WE SHOULD ALSO GET 2 WHEN WE COMPUTE THIS AND THIS
GIVEN BY THE EXPONENT POWER RULE.
WELL, 3 TO THE 2nd IS EQUAL TO 9, 9 MOD 7 WOULD GIVE US 2,
SO THIS IS EQUAL TO 2 TO THE 4th MOD 7.
AND 2 TO THE 4th = 16, 16 MOD 7 = 2.
THERE ARE 2 7s IN 16, 2 x 7 = 14, AND 16 - 14 = 2.
NEXT, 3 TO THE 4th = 81,
SO THIS WOULD BE EQUIVALENT TO 81 MOD 7
RAISED TO THE 2nd MOD 7.
SO WE'LL DIVIDE 81 BY 7, SUBTRACT 11 x 7,
SO THIS GIVES US 4.
SO HERE WE'D HAVE 4 SQUARED MOD 7 WHICH GIVES US 16 MOD 7
WHICH IS WHAT WE HAD BEFORE WHICH WE KNOW = 2.
SO THIS DOES VERIFY THE MODULAR EXPONENT POWER RULE.
I THINK WE'LL STOP HERE FOR THIS LESSON.
I HOPE YOU FOUND THIS HELPFUL.