Posts

Showing posts from December, 2021

Introduction to Modular Arithmetic, Part 1

See all posts in this series I have mentioned modular arithmetic (sometimes known as "clock arithmetic") in several of my posts. But this may not be helpful if you haven't come across this type of arithmetic before.

Using modular arithmetic to help calculate Greatest Common Divisors

In a recent FPM class we discussed how to determine \mathrm{GCD}(21,2^{70}+5). [See also my earlier post on Greatest Common Divisors ] The answer here was that 21 \mathrel{|} 2^{70}+5 and so \mathrm{GCD}(21,2^{70}+5) = 21\,. We discussed various ways to prove this. Some students had shown separately that 3 \mathrel{|} 2^{70}+5 and 7 \mathrel{|} 2^{70}+5, from which it follows, e.g. by prime factorization (Fundamental Theorem of Arithmetic, FTA), or by more elementary means, that 21 \mathrel{|} 2^{70}+5 too. In the Engagement Session we showed, instead, that 2^{70} \equiv 2^4 = 16  (\mathrm{mod}~ 21), which gives us 2^{70}+5 \equiv 16+5 = 21 \equiv 0  (\mathrm{mod}~ 21) and so 21 \mathrel{|} 2^{70}+5. We discovered that 2^{70} \equiv 2^4  (\mathrm{mod}~ 21) by looking at powers of 2 mod 21, and spotting that we had a repeating pattern with period 6 , so that 2^{70}=2^{4+66} \equiv 2^4 \((\mathrm{mod}~ 2...

The Christmas Equation

I recently posted the following on this year's FPM Piazza forum. Hi everyone, I saw this a few years ago on QI, and found another version on the web at http://mathandmultimedia.com/2014/12/02/merry-christmas-equation/ If we are told that y=\frac{\ln(\frac{x}m-sa)}{r^2}