Modular Arithmetic
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.
Note by
Calvin Lin
7 years, 7 months ago
No vote yet
16 votes
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
What are the last three digits of 999?
Log in to reply
We have 950≡1 (1000) and 99≡39 (50). Hence 999≡939≡289 (1000).
Is there a positive integer n for which n7−77 is a Fibonacci number?
Log in to reply
n7≡0,1,12,17,28(mod29)
n7−77≡9,10,11,22,27(mod29)
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.
Log in to reply
Can you explain why you chose modulo 29? That seems like such a random number.
Log in to reply
Seven 7th roots of unity modulo 29, so only 1+4=5 seventh powers, which gives a fighting chance of the residues for n7−77 being distinct from the Fibonacci residues.
Log in to reply
Indeed. A clearer explanation of the motivation, is to say that if p is a prime of the form 7k+1, then there are k+1 seventh powers (where the +1 accounts for 0 ). This gives a fighting change of the residues being distinct from the Fibonacci residues. So, we try the smallest prime of the form 7k+1, which is 29. Had it not worked, we will look at 43, so on and so forth.
Writing it this way takes away the mysticism of "why 29", and provides a path to approach the more general problem.
Here are a few easy ones I know about modular arithmetic:
The fractional part of 7n is .142857 repeating, or some variant thereof. What is the minimal positive integer N such that the fractional part of 7251×n is .142857 repeating?
Log in to reply
Nice questions. I took the liberty of removing the answers and splitting out the questions, so that people can comment on them individually.
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≡6(mod7). In order for 7251×n to be 0.142857 repeating, 251n≡1(mod7). Looking at the first congruence, we can start by realizing that 251n will have a remainder of 1 iff 6n≡1(mod7). 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
Your formatting is fine. Note, though, that you could simplify things a bit by making 251≡−1(mod7).
Find all perfect squares such that they are divisible by 2 and not 4.
Log in to reply
Nothing, because the square root of 4 is 2 and 2 square is 4.
nothing, it is impossible. Because, square root of 4 is 2, and 2 square is 4.
All even numbers squared give an even number squared. An even number can be expressed by 2n, 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.
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?
Log in to reply
Ah, you got me. I was hoping that would fly beneath the radar.
To answer this question well, you have to accurately account for all of the leap years, and their effects on the calendar.
Log in to reply
But an even more trick question: are we supposed to accommodate for the 1752 calendar change?
Log in to reply
The Gregorian calendar was implemented in 1582 (which was why I chose 1600).
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.
No, the calendar change is trivial, and is left as an exercise to the reader.
Reply to Calvin, 1. In a 400-year cycle, there are 58 years was the first of January celebrated on a Sunday.
What are the last three digits of 200320022001?