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?

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

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

Note by Calvin Lin
5 years, 12 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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

What are the last three digits of 999 9^{9^9} ?

Michael Tong - 5 years, 12 months ago

Log in to reply

We have 95019^{50} \equiv 1 (10001000) and 99399^9 \equiv 39 (5050). Hence 9999392899^{9^9} \equiv 9^{39} \equiv 289 (10001000).

Mark Hennings - 5 years, 11 months ago

Log in to reply

  1. Given any year, find the date of Easter (assuming the Gregorian Calendar!).

  2. Is there a positive integer nn for which n777n^7 - 77 is a Fibonacci number?

Mark Hennings - 5 years, 12 months ago

Log in to reply

n70,1,12,17,28(mod29)n^7 \equiv 0, 1, 12, 17, 28 \pmod {29}

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

The pisano period of 2929 is 1,1,2,3,5,8,13,21,5,26,2,28,1,01, 1, 2, 3, 5, 8, 13, 21, 5, 26, 2, 28, 1, 0, none of the values are the same.

Michael Tong - 5 years, 11 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 11 months ago

Log in to reply

@Calvin Lin Seven 77th roots of unity modulo 2929, so only 1+4=51+4=5 seventh powers, which gives a fighting chance of the residues for n777n^7-77 being distinct from the Fibonacci residues.

Mark Hennings - 5 years, 11 months ago

Log in to reply

@Mark Hennings Indeed. A clearer explanation of the motivation, is to say that if pp is a prime of the form 7k+1 7k + 1 , then there are k+1 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 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.

Calvin Lin Staff - 5 years, 11 months ago

Log in to reply

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

The fractional part of n7\frac {n}{7} is .142857.142857 repeating, or some variant thereof. What is the minimal positive integer N such that the fractional part of 2517×n\frac{251}{7} \times n is .142857.142857 repeating?

Michael Tong - 5 years, 12 months ago

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.

Calvin Lin Staff - 5 years, 12 months ago

Log in to reply

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 251251, which can be written as 2516(mod7)251 \equiv 6 \pmod{7}. In order for 2517×n\frac {251}{7} \times n to be 0.1428570.142857 repeating, 251n1(mod7)251n \equiv 1 \pmod{7}. Looking at the first congruence, we can start by realizing that 251n251n will have a remainder of 11 iff 6n1(mod7)6n \equiv 1 \pmod{7}. We can see that the possible values for nn will be of the form 7k17k - 1, where kk is a positive integer. Therefore, the minimum possible value for nn is 66.

Parth Chopra - 5 years, 11 months ago

Log in to reply

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

Bob Krueger - 5 years, 11 months ago

Log in to reply

Find all perfect squares such that they are divisible by 2 and not 4.

Michael Tong - 5 years, 12 months ago

Log in to reply

Nothing, because the square root of 4 is 2 and 2 square is 4.

Wahyu Adi Saputro - 5 years, 11 months ago

Log in to reply

nothing, it is impossible. Because, square root of 4 is 2, and 2 square is 4.

Wahyu Adi Saputro - 5 years, 11 months ago

Log in to reply

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.

Anton Than Trong - 5 years, 11 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 - 5 years, 12 months ago

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.

Calvin Lin Staff - 5 years, 12 months ago

Log in to reply

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

Bob Krueger - 5 years, 12 months ago

Log in to reply

@Bob Krueger 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.

Calvin Lin Staff - 5 years, 12 months ago

Log in to reply

@Bob Krueger No, the calendar change is trivial, and is left as an exercise to the reader.

Michael Tong - 5 years, 12 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 - 5 years, 11 months ago

Log in to reply

What are the last three digits of 2003200220012003^{2002^{2001}}?

Tong Zou - 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...