This week, we learn about Modular Arithmetic, a system of arithmetic for the integers with many applications.

How would you use Modular Arithmetic to solve the following?

In the years 1600-1999, how many times was the first of January celebrated on a Sunday?

Share a question which can easily be approached by Modular Arithmetic.

## Comments

Sort by:

TopNewestIs there a positive integer \(n\) for which \(n^7 - 77\) is a Fibonacci number?

Log in to reply

\(n^7 - 77 \equiv 9, 10, 11, 22, 27 \pmod {29}\)

The pisano period of \(29\) is \(1, 1, 2, 3, 5, 8, 13, 21, 5, 26, 2, 28, 1, 0\), none of the values are the same. – Michael Tong · 3 years, 10 months ago

Log in to reply

– Calvin Lin Staff · 3 years, 10 months ago

Can you explain why you chose modulo 29? That seems like such a random number.Log in to reply

– Mark Hennings · 3 years, 10 months ago

Seven \(7\)th roots of unity modulo \(29\), so only \(1+4=5\) seventh powers, which gives a fighting chance of the residues for \(n^7-77\) being distinct from the Fibonacci residues.Log in to reply

Writing it this way takes away the mysticism of "why 29", and provides a path to approach the more general problem. – Calvin Lin Staff · 3 years, 10 months ago

Log in to reply

What are the last three digits of \( 9^{9^9} \)? – Michael Tong · 3 years, 10 months ago

Log in to reply

– Mark Hennings · 3 years, 9 months ago

We have \(9^{50} \equiv 1\) (\(1000\)) and \(9^9 \equiv 39\) (\(50\)). Hence \(9^{9^9} \equiv 9^{39} \equiv 289\) (\(1000\)).Log in to reply

Here are a few easy ones I know about modular arithmetic:

The fractional part of \(\frac {n}{7}\) is \(.142857\) repeating, or some variant thereof. What is the minimal positive integer N such that the fractional part of \(\frac{251}{7} \times n\) is \(.142857\) repeating? – Michael Tong · 3 years, 10 months ago

Log in to reply

– Parth Chopra · 3 years, 10 months ago

Sorry, I'm a new member, so I don't really know the formatting that well yet. We can start this problem by thinking about the number \(251\), which can be written as \(251 \equiv 6 \pmod{7}\). In order for \(\frac {251}{7} \times n\) to be \(0.142857\) repeating, \(251n \equiv 1 \pmod{7}\). Looking at the first congruence, we can start by realizing that \(251n\) will have a remainder of \(1\) iff \(6n \equiv 1 \pmod{7}\). We can see that the possible values for \(n\) will be of the form \(7k - 1\), where \(k\) is a positive integer. Therefore, the minimum possible value for \(n\) is \(6\).Log in to reply

– Bob Krueger · 3 years, 9 months ago

Your formatting is fine. Note, though, that you could simplify things a bit by making \(251 \equiv -1 \pmod 7\).Log in to reply

– Calvin Lin Staff · 3 years, 10 months ago

Nice questions. I took the liberty of removing the answers and splitting out the questions, so that people can comment on them individually.Log in to reply

Find all perfect squares such that they are divisible by 2 and not 4. – Michael Tong · 3 years, 10 months ago

Log in to reply

n, where n is any integer. Thus, an even number squared can be expressed as 2^2n^2, which is 4n^2. Thus, no perfect squares are divisible by 2 and not 4. – Anton Than Trong · 3 years, 9 months agoLog in to reply

– Wahyu Adi Saputro · 3 years, 10 months ago

nothing, it is impossible. Because, square root of 4 is 2, and 2 square is 4.Log in to reply

– Wahyu Adi Saputro · 3 years, 10 months ago

Nothing, because the square root of 4 is 2 and 2 square is 4.Log in to reply

What are the last three digits of \(2003^{2002^{2001}}\)? – Tong Zou · 3 years, 8 months ago

Log in to reply

Reply to Calvin, 1. In a 400-year cycle, there are 58 years was the first of January celebrated on a Sunday. – Philips Zephirum Lam · 3 years, 10 months ago

Log in to reply

For the first question, are we assuming that leap years happen every 4 years, or are we following the leap year rules and omitting the leap year on 1700, 1800, and 1900? – Daniel Liu · 3 years, 10 months ago

Log in to reply

To answer this question well, you have to accurately account for all of the leap years, and their effects on the calendar. – Calvin Lin Staff · 3 years, 10 months ago

Log in to reply

– Bob Krueger · 3 years, 10 months ago

But an even more trick question: are we supposed to accommodate for the 1752 calendar change?Log in to reply

– Michael Tong · 3 years, 10 months ago

No, the calendar change is trivial, and is left as an exercise to the reader.Log in to reply

Not my fault that Britain (and her colonies) were late to the party.

FYI: The gregorian calendar was adopted at different points in time. Note that not everyone use the gregorian calendar. – Calvin Lin Staff · 3 years, 10 months ago

Log in to reply