5/4/22, 6:20 PM 3085 Intermediate Number Theory

Intermediate Number Theory (3085)

Joshua Zucker

Thursday
Apr 28, 2022 - Jul 14, 2022
7:30 - 9:00 PM ET (4:30 - 6:00 PM PT)

Overview
Week 1 (Apr 28) Class Transcript - Introduction
< Go back to the class overview page
Copyright © AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you
cannot share the contents of this file with others.
Display all student messages • Show few student messages • Hide student messages
joshuazucker 2022-04-28 19:22:03
ART OF PROBLEM SOLVING - Intermediate Number Theory

joshuazucker 2022-04-28 19:22:07

Hello and welcome to the Intermediate Number Theory class!

joshuazucker 2022-04-28 19:22:11

My name is Joshua Zucker and I am the instructor for this course.

joshuazucker 2022-04-28 19:22:24

Here's some stuff about me:

Joshua Zucker joined AoPS as a part-time instructor in 2007. He discovered his love for number theory at Dr. Arnold Ross's
summer program at Ohio State University more than 30 years ago. Joshua has been a Math Olympiad Summer Program invitee, a
member of the first US Physics Olympiad team, and a top-10 scorer on the Putnam. He holds a BS in physics and an MS in
mathematics from Stanford, as well as an MS in astrophysics from UC Berkeley. A former problem writer for MATHCOUNTS,
Joshua also co-founded the Julia Robinson Mathematics Festival and the Math Teachers' Circle. In 2019, he placed 3rd in his
division at the World Sudoku Championships.

joshuazucker 2022-04-28 19:22:43

Before we get started, I'd like to discuss a few details about our classroom!

joshuazucker 2022-04-28 19:22:45

Try typing "Hi!"

joshuazucker 2022-04-28 19:23:19

Oh, you see the message, but it says "sent to instructor"?

joshuazucker 2022-04-28 19:23:20

That's because...

joshuazucker 2022-04-28 19:23:22

The classroom is now moderated. This means that the messages you type will come to the instructors rather than going directly
into the room. We'll choose some of the messages to share with all the students.

joshuazucker 2022-04-28 19:23:31

I'll go ahead and choose some of your messages to share now!

vanlucas 2022-04-28 19:23:43

Hi!

GarudS 2022-04-28 19:23:43

hi

vanlucas 2022-04-28 19:23:43

Hi

[Link] 1/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 19:23:47

It worked! Now you can see your messages.

joshuazucker 2022-04-28 19:23:50

Once class begins, please feel free to ask questions at any time. Rather than going into the room, your questions will go directly to
me or one of the assistants, and we'll help you out!

joshuazucker 2022-04-28 19:23:54

Go ahead and ask some questions now to try it out!

joshuazucker 2022-04-28 19:24:10

Or, let me know if this is your first ever AoPS Online class!

vanlucas 2022-04-28 19:24:14

Whats 1 + 1?

welxia88 2022-04-28 19:24:14

1+1?!?!

joshuazucker 2022-04-28 19:24:25

It's equal to 0 + 2.

joshuazucker 2022-04-28 19:24:54

As you might have just experienced if you asked a question, sometimes we'll whisper quick comments to you. If you have a bigger
question that requires a back-and-forth conversation, we'll open a private message window with you and chat one-on-one.

joshuazucker 2022-04-28 19:25:00

Sometimes we like to show images in the classroom! Let's test out the software real quick to make sure everyone can see them.

joshuazucker 2022-04-28 19:25:02

joshuazucker 2022-04-28 19:25:03

joshuazucker 2022-04-28 19:25:08

If you can see the two images I just sent, it's working! But also, it's a spot the difference puzzle!

joshuazucker 2022-04-28 19:25:11

What's the difference between the two images?

rsun 2022-04-28 19:26:54

The links are different

Lionking212 2022-04-28 19:26:54

the bottom link

[Link] 2/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

GarudS 2022-04-28 19:26:54

The URL (i did this 1 million times)

joshuazucker 2022-04-28 19:26:58

You got it! They're the same except for the labels. Good eye!

joshuazucker 2022-04-28 19:27:00

Actually, we have one more image for you. If you can see it, then the software is working.

joshuazucker 2022-04-28 19:27:01

joshuazucker 2022-04-28 19:27:09

If you don't see a smiley-face image, just say something and one of us can help you fix the issue.

joshuazucker 2022-04-28 19:27:16

What happens when you double-click on the smiley-face?

vanlucas 2022-04-28 19:28:13

a window pops out

MatthewS192 2022-04-28 19:28:13

A window pops up

Andrew_Dou 2022-04-28 19:28:13

it pops up in a window

joshuazucker 2022-04-28 19:28:16

Oh yeah! It opens up in a new window. This can be useful if you want to keep the image around while everyone keeps typing more
stuff into the classroom.

joshuazucker 2022-04-28 19:28:21

There is no audio nor live video in the classroom. If you want to read more about why we chose to have no audio/video in the
classroom, you can read this link (after class):

joshuazucker 2022-04-28 19:28:31

[Link]

joshuazucker 2022-04-28 19:28:34

If you want more detailed information about how to operate the classroom you can find that here:

joshuazucker 2022-04-28 19:28:42

[Link]

joshuazucker 2022-04-28 19:28:46

Also, students can use LaTeX in the classroom, just like on the message board. Specifically, place your math LaTeX code inside
dollar signs. For example, type:

joshuazucker 2022-04-28 19:28:48

We know that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.

joshuazucker 2022-04-28 19:28:51

This should give you:

joshuazucker 2022-04-28 19:28:53

We know that .
1 1 5
+ =
2 3 6

Andrew_Dou 2022-04-28 19:29:43

We know that
1 1 5
+ =
2 3 6

[Link] 3/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

vanlucas 2022-04-28 19:29:43

1 1 5

2
+
3
=
6
.

mathtennis 2022-04-28 19:29:43

We know that .
1 1 5
+ =
2 3 6

joshuazucker 2022-04-28 19:29:47

If you don't know LaTeX, that's no big deal. You don't have to use it. We'll tell you how to express different symbols in plain text as
we encounter them.

joshuazucker 2022-04-28 19:29:52

If you are unfamiliar with LaTeX and would like to learn more about how to use it, we have a LaTeX Guide in the Resources area of
our site. The Message Board is also a good place to practice using LaTeX.

joshuazucker 2022-04-28 19:29:58

Your Intermediate Number Theory course Message Board can be found here:

[Link]

There's also a link to the message board on the course homepage.

joshuazucker 2022-04-28 19:30:05

Additionally, we have Office Hours: an AoPS staff member will be on the message board to answer questions in real time every day
from 4:00 - 5:30 PM ET (1:00 - 2:30 PM PT) and 7:30-8:30 PM ET (4:30-5:30 PM PT).

joshuazucker 2022-04-28 19:30:25

And now it's time to start class for real! For those just arriving, we'll go through some of that same stuff, only more quickly this
time.

joshuazucker 2022-04-28 19:30:57

Please let us know if you are (1) here for your very first AoPS class and (2) arrived within the last couple minutes. Then we can
offer a little extra help.

joshuazucker 2022-04-28 19:31:02

But for now:

joshuazucker 2022-04-28 19:31:03

Hello and welcome to the Intermediate Number Theory class!

joshuazucker 2022-04-28 19:31:06

My name is Joshua Zucker and I am the instructor for this course.

joshuazucker 2022-04-28 19:31:12

Here's some stuff about me:

Joshua Zucker joined AoPS as a part-time instructor in 2007. He discovered his love for number theory at Dr. Arnold Ross's
summer program at Ohio State University more than 30 years ago. Joshua has been a Math Olympiad Summer Program invitee, a
member of the first US Physics Olympiad team, and a top-10 scorer on the Putnam. He holds a BS in physics and an MS in
mathematics from Stanford, as well as an MS in astrophysics from UC Berkeley. A former problem writer for MATHCOUNTS,
Joshua also co-founded the Julia Robinson Mathematics Festival and the Math Teachers' Circle. In 2019, he placed 3rd in his
division at the World Sudoku Championships.

joshuazucker 2022-04-28 19:31:23

Before we get started, I'd like to discuss a few details about our clean and shiny classroom!

joshuazucker 2022-04-28 19:31:34

Try typing "I love number theory!"

joshuazucker 2022-04-28 19:31:45

Oh, you see the message, but it says "sent to instructor"?

joshuazucker 2022-04-28 19:31:47

[Link] 4/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
That's because...

joshuazucker 2022-04-28 19:31:50

The classroom is now moderated. This means that the messages you type will come to the instructors rather than going directly
into the room. We'll choose some of the messages to share with all the students.

joshuazucker 2022-04-28 19:31:54

I'll go ahead and choose some of your messages to share now!

lihao_david 2022-04-28 19:31:57

I love number theory!

GarudS 2022-04-28 19:31:57

I love number theory!

Andrew_Dou 2022-04-28 19:31:57

I love number theory!

joshuazucker 2022-04-28 19:32:15

It worked! Now you can see your messages.

joshuazucker 2022-04-28 19:32:19

Once class begins, please feel free to ask questions at any time. Rather than going into the room, your questions will go directly to
me or one of the assistants, and we'll help you out!

joshuazucker 2022-04-28 19:32:22

Go ahead and ask some questions now to try it out!

MatthewS192 2022-04-28 19:32:58

Is this statement true?

joshuazucker 2022-04-28 19:33:02

Maybe!

MathHayden 2022-04-28 19:33:06

what's your favorite food

joshuazucker 2022-04-28 19:33:12

Sushi. Ice cream. ... sushi ice cream?

gladIasked 2022-04-28 19:33:44

how do aops instructors type to fast

joshuazucker 2022-04-28 19:33:59

Some of us say we are mutants with 26 fingers (plus thumbs for shift and space).

joshuazucker 2022-04-28 19:34:03

Others say we use two keyboards.

joshuazucker 2022-04-28 19:34:12

I'm not clear on whether that's one for each hand, or one for hands and one for feet?

VDR 2022-04-28 19:34:18

copy and paste

SIYQ 2022-04-28 19:34:18

practice?

vanlucas 2022-04-28 19:34:18

they are pro typists

joshuazucker 2022-04-28 19:34:24

Those are possible hypotheses too.

joshuazucker 2022-04-28 19:34:55

[Link] 5/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
Also, we sometimes make typos, but that's because we're human, not artificial intelligences that teach these classes. Humans
make typos, right? That's a thing humans do sometmies?

joshuazucker 2022-04-28 19:35:04

As you might have just experienced if you asked a question, sometimes we'll whisper quick comments to you. If you have a bigger
question that requires a back-and-forth conversation, we'll open a private message window with you and chat one-on-one.

justJen 2022-04-28 19:35:11

sometimes*

joshuazucker 2022-04-28 19:35:26

See! I'm totally human. It's clear now. Typos! That's your evdience right there.

joshuazucker 2022-04-28 19:35:29

Most of the time those whispers will come from your class assistants. Let's say hi to them now!

joshuazucker 2022-04-28 19:35:35

Your assistants for this course will be Margaret Esther Chua Cruz (yu_margaret) and Pavle Martinovic (pavleto00).

joshuazucker 2022-04-28 19:35:40

yu_margaret: Margaret Esther Cruz is currently pursuing her bachelor's degree in Mathematics at the University of the Philippines-
Diliman. She discovered her love for mathematics at the early age of 4 years old and has always shown enthusiasm in solving
math problems. Ever since she was 5 years old, she has been joining local mathematics competitions. She also belonged to a
roster of students from the Philippines who are sent to international mathematics competitions. She has always dreamed of
joining a mathematical olympiad competition, but over the past few years, she has become more fond of mathematical modeling.
She really loves learning and she thinks that being part of AoPS is the best opportunity for her to share her knowledge in
Mathematics and at the same time, learn some new skills. Besides Mathematics, she also loves studying Physics, learning
musical instruments, singing, baking, and watching Spanish shows - which led her to start learning the Spanish language.

yu_margaret 2022-04-28 19:35:47

Hello!

lihao_david 2022-04-28 19:35:50

hi

Andrew_Dou 2022-04-28 19:35:50

Hi!

justJen 2022-04-28 19:35:50

hi!!

joshuazucker 2022-04-28 19:35:54

pavleto00: Pavle joined AoPS in 2020, while searching for an adventure. He represented Serbia at the 2017, 2018 and 2019
International Mathematical Olympiads, winning a silver and 2 gold medals, respectively. He has also participated at Romanian
Masters of Mathematics 2017, 2018 and 2019, winning one gold and 2 bronze medals. A native of Belgrade, Serbia, Pavle is
earning a Bachelor's degree in mathematics and informatics from the University of Belgrade. His interests include playing football,
volleyball, and all kinds of sports with a ball. He is currently participating in bridge tournaments and enjoys the game a lot.

pavleto00 2022-04-28 19:35:57

Hi, everyone!

mathfunyay 2022-04-28 19:36:06

Hi!

MathHayden 2022-04-28 19:36:06

hi

hujenny2008 2022-04-28 19:36:06

hi

joshuazucker 2022-04-28 19:36:40

Hmmm, can artificial intelligences do that or are we all programmed, er, I mean, are they all programmed to spell correctly?

joshuazucker 2022-04-28 19:36:49

[Link] 6/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
Sometimes we like to show images in the classroom! Let's test out the software real quick to make sure everyone can see them.

joshuazucker 2022-04-28 19:36:53

joshuazucker 2022-04-28 19:36:54

joshuazucker 2022-04-28 19:37:06

If you can see two copies of the AoPS logo with different URLs, things are working well!

joshuazucker 2022-04-28 19:37:13

Also, if you can see this smiley face:

joshuazucker 2022-04-28 19:37:14

joshuazucker 2022-04-28 19:37:19

then that's good.

joshuazucker 2022-04-28 19:37:29

If you can't see a smiley there, tell us so that we can help you sort out why not!

joshuazucker 2022-04-28 19:37:44

If you double click the smiley (or any post), it opens in a new window.

joshuazucker 2022-04-28 19:37:49

There is no audio nor live video in the classroom. If you want to read more about why we chose to have no audio/video in the
classroom, you can read this link (after class): [Link]

joshuazucker 2022-04-28 19:37:55

If you want more detailed information about how to operate the classroom you can find that here:
[Link]

joshuazucker 2022-04-28 19:38:08

Also, students can use LaTeX in the classroom, just like on the message board. Specifically, place your math LaTeX code inside
dollar signs. For example, type:

joshuazucker 2022-04-28 19:38:09

We know that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.

joshuazucker 2022-04-28 19:38:11

This should give you:

[Link] 7/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 19:38:13

5
We know that .
1 1
+ =
2 3 6

Lucasfunnyface 2022-04-28 19:38:53

1 1 5
We know that 2
+ = .
3 6

SIYQ 2022-04-28 19:38:53

1 1 5

2
+
3
=
6
.

gladIasked 2022-04-28 19:38:53

1 1 5
+ =
2 3 6

joshuazucker 2022-04-28 19:38:58

If you don't know LaTeX, that's no big deal. You don't have to use it. We'll tell you how to express different symbols in plain text as
we encounter them.

joshuazucker 2022-04-28 19:39:00

If you are unfamiliar with LaTeX and would like to learn more about how to use it, we have a LaTeX Guide in the Resources area of
our site. The Message Board is also a good place to practice using LaTeX. You can also right-click on things in the classroom and
choose Show Math As, TeX Commands, to see how we typed it.

Lionking212 2022-04-28 19:39:04

We know that . We also know that 1 and 1 + 1
1 1 5
+ ≠ ≠ 1 ≠ 2
2 3 6

joshuazucker 2022-04-28 19:39:13

Contradiction! Error! Rebooting ... please wait.

joshuazucker 2022-04-28 19:39:27

Um, I mean, haha, that was funny!

joshuazucker 2022-04-28 19:39:34

Your Intermediate Number Theory course Message Board can be found here:

[Link]

There's also a link to the message board on the course homepage.

joshuazucker 2022-04-28 19:39:41

Additionally, we have Office Hours: an AoPS staff member will be on the message board to answer questions in real time every day
from 4:00 - 5:30 PM ET (1:00 - 2:30 PM PT) and 7:30-8:30 PM ET (4:30-5:30 PM PT).

joshuazucker 2022-04-28 19:39:52

You can also change the classroom size, font size, colors, and other settings in the Settings Menu at the top-right of your screen.
"Flashing notifications" determines if your private message window will blink/flash with a number of unread messages when you
receive one, or if it should only display the static number.

joshuazucker 2022-04-28 19:39:58

We will also post "sticky" problems and important comments to the top of the room. Like this one!

joshuazucker 2022-04-28 19:40:02

You can slide the bar between the "sticky" portion of the room on the top of the classroom and the rest of the classroom to make it
larger or smaller. Doing this will help you read the sticky area and the classroom.

joshuazucker 2022-04-28 19:40:07

At the end of class, we'll talk about homework and other class procedures. But for now, let's get going on the math.

joshuazucker 2022-04-28 19:40:15

Intermediate Number Theory Week 1: Introduction

joshuazucker 2022-04-28 19:40:23

For most of the course, we will explore one major theme or topic each week. But today, we'll do more of a "sampler" of problems,
which will help get you comfortable with some techniques we'll use a lot.

[Link] 8/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 19:40:35

The overall theme for today, as well as most of the early weeks of this course, is mixing basic techniques of algebra (variable
assignment, factoring, etc.) with number theory concepts (such as divisibility, parity, and remainders). These are particularly
applicable to most number theory problems you might find on the AMC or AIME.

joshuazucker 2022-04-28 19:40:53

In the latter half of the course, we'll be jumping into some more theoretical ideas, which will introduce number theory concepts
commonly seen at the easy olympiad level, or the level of the first few weeks of a university number theory course. But that will
wait for a bit; we certainly won't see it today.

joshuazucker 2022-04-28 19:41:00

MAKING USE OF VARIABLES IN NUMBER THEORY

joshuazucker 2022-04-28 19:41:08

Many of the kinds of algebraic tools that we will cover today are discussed in greater detail in our Algebra classes. Today our focus
is on applying these methods to number theory problems.

joshuazucker 2022-04-28 19:41:23

The perimeter of an equilateral triangle exceeds the perimeter of a square by 1989 cm. The length of each side of the triangle
exceeds the length of each side of the square by d cm. The square has a perimeter greater than 0. How many positive integers are
NOT possible values for d?

joshuazucker 2022-04-28 19:41:57

I'll let you think for a minute about the problem. When you give an answer or partial answer, please include some justification as
well. I'll pass responses through, and then we'll go through the details of the solution.

joshuazucker 2022-04-28 19:42:21

It's best to give just a first step or two of the solution with some explanation, so that I can share your comment with the other
students and give them some help without spoiling the whole problem for them.

MathHayden 2022-04-28 19:42:49

set variables for side lengths of the triangle and square

joshuazucker 2022-04-28 19:42:59

That's a good way to start! We'll let the side length of the equilateral triangle be x, and the side length of the square be y. What
equations do we have in terms of x and y?

mathtennis 2022-04-28 19:44:15

3x=1989+4y

lihao_david 2022-04-28 19:44:15

3x − 4y = 1989

MatthewS192 2022-04-28 19:44:15

3x − 4y = 1989 ?

joshuazucker 2022-04-28 19:44:27

Great! The first sentence says that the perimeter of the triangle is 1989 larger than the perimeter of the square. So

3x = 4y + 1989.

joshuazucker 2022-04-28 19:44:31

The second sentence says that the triangle's sides are d longer than the square's. So

x = y + d.

joshuazucker 2022-04-28 19:44:35

What next?

joshuazucker 2022-04-28 19:46:02

(By the way, there were a lot of sign errors in your equation. Be sure to check! Think something like "if the perimeter of the square
4y is 4 then the triangle perimeter would be 1989 + 4 = 1993 = 3x, so when you write your equation you'll definitely notice if

[Link] 9/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
you write it the wrong way around, like 3x + 1989 = 4y or something.)

happyhari 2022-04-28 19:46:16

substitute the value of x in the second equation into the first equationj

Ihatebar 2022-04-28 19:46:16

substitution?

mikeguylol 2022-04-28 19:46:16

substitution

joshuazucker 2022-04-28 19:46:30

Yeah! We want to do some substitution or elimination. We're interested in the variable d here, so x and y are a nuisance in
comparison. Let's get rid of one of them.

Pokegirl112 2022-04-28 19:46:38

Substitute the second equation into the first to get 3(y + d) = 4y + 1989.

mathfunyay 2022-04-28 19:46:38

Substitute y + d for x.

joshuazucker 2022-04-28 19:46:49

OK, there are other ways but that's a popular one with a lot of you.

euler12345 2022-04-28 19:47:00

Substitute x = y + d into the first equation

AlextheGreatest 2022-04-28 19:47:00

substitution of x = y + d into 3x = 4y + 1989

hujenny2008 2022-04-28 19:47:00

3(y+d)=4y+1989

joshuazucker 2022-04-28 19:47:04

We can plug x = y + d into the first equation to get 3(y + d) = 4y + 1989.

joshuazucker 2022-04-28 19:47:06

We can then expand and collect the y terms together to get 3d = y + 1989. Now what?

lihao_david 2022-04-28 19:47:59

build an inequality by assigning a minimum value to y

euler12345 2022-04-28 19:47:59

y must be positive, so 3d > 1989?

lihao_david 2022-04-28 19:48:02

build an inequality by setting y to its minimum (0)

joshuazucker 2022-04-28 19:48:15

We see from the above that for any given value of d, we have y = 3d − 1989. Since x = y + d, we have x = 4d − 1989.

joshuazucker 2022-04-28 19:48:24

We need x, y > 0. How do we proceed from there?

andlind 2022-04-28 19:49:02

d = (y + 1989)/3

joshuazucker 2022-04-28 19:49:18

That's a fine way too! If you look at it that way, knowing what we know about y, what's the smallest possible positive integer value
of d?

Andrew_Dou 2022-04-28 19:49:23

we need 4d − 1989 > 0 and 3d − 1989 > 0

joshuazucker 2022-04-28 19:49:29

Yup, that's a good alternative too.
[Link] 10/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

xixinyc 2022-04-28 19:49:45

3d>1989

rsun 2022-04-28 19:49:54

since y > 0, 3d > 1989

joshuazucker 2022-04-28 19:50:08

Yup. For y > 0, we need 3d > 1989 or d > 663. Since y > 0, d > 0, and x = y + d, we certainly have x > 0. So d > 663 is
all we need for x, y > 0. That is, d can be any positive integer greater than 663.

joshuazucker 2022-04-28 19:50:33

And conversely, when d is greater than 663, then x and y are both positive.

joshuazucker 2022-04-28 19:50:36

So what's the answer to the problem?

Mahika_reddy 2022-04-28 19:50:56

663

MathHayden 2022-04-28 19:50:56

663

wengyt96 2022-04-28 19:50:56

663?

joshuazucker 2022-04-28 19:51:01

There are 663 positive integers that d cannot be, namely the numbers 1, 2, 3, … , 663.

joshuazucker 2022-04-28 19:51:10

What is the smallest positive integer that can be expressed as the sum of nine consecutive integers, the sum of ten consecutive
integers, and the sum of eleven consecutive integers?

joshuazucker 2022-04-28 19:51:36

How should we start?

MathHayden 2022-04-28 19:52:05

let the integer be n?

lihao_david 2022-04-28 19:52:05

express each summation algebraically

joshuazucker 2022-04-28 19:52:20

Giving things names is great, and so is translating the words into algebra. Good start!

joshuazucker 2022-04-28 19:52:36

Let's look at the first condition: our number is the sum of nine consecutive integers. We can let n be the sum of the nine integers.
(We'll need the same n later for the other conditions, so we may as well set it up now.)

joshuazucker 2022-04-28 19:52:59

How should we express "n is the sum of nine consecutive integers" in algebraic language?

MathHayden 2022-04-28 19:53:33

the mean of the nine consecutive integers is n/9

hujenny2008 2022-04-28 19:53:33

the middle number of the sum of 9 numbers has to be an integer, so let that be n/9

GarudS 2022-04-28 19:53:33

9x = n

joshuazucker 2022-04-28 19:53:47

Yeah! We could let some letter stand for the first of the nine integers, but that is throwing out some wonderful symmetry.

joshuazucker 2022-04-28 19:54:09

Instead, for the nine integers themselves, let's set x to be the median of the nine integers. Symmetry! I love it!

[Link] 11/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 19:54:28

The nine integers are those from x − 4 to x + 4 inclusive, so we get

n = (x − 4) + (x − 3) + ⋯ + (x + 3) + (x + 4) = 9x.

joshuazucker 2022-04-28 19:54:43

Or, maybe it's clear that there are 9 integers whose average is the middle value, x, so the sum is 9x.

Bananaman27 2022-04-28 19:54:51

n is divisible by 9?

Andrew_Dou 2022-04-28 19:54:51

n = 9a for some integer a

xixinyc 2022-04-28 19:54:51

n = 9x

joshuazucker 2022-04-28 19:55:16

Exactly, the equations are a way of writing the English statement "n is divisible by 9" or "n is a multiple of 9" in math.

joshuazucker 2022-04-28 19:55:26

We conclude that n can be written as the sum of nine consecutive integers if and only if it is a multiple of 9.

joshuazucker 2022-04-28 19:55:33

How about if n is the sum of ten consecutive integers?

wengyt96 2022-04-28 19:56:47

the two middle values add up to n/5?

MathHayden 2022-04-28 19:56:47

the mean is y 1/2 (not an integer) for some integer y

hujenny2008 2022-04-28 19:56:47

the middle number must be a number with .5 so n has to be divisible by 5

joshuazucker 2022-04-28 19:56:56

Yeah, there is no middle integer this time.

joshuazucker 2022-04-28 19:57:11

We could let the middle value be a half-integer (that is, half of an odd integer) and work from there.

joshuazucker 2022-04-28 19:57:26

Or we could damage the symmetry a little bit but have a variable that is an integer, like the fifth of the ten numbers.

joshuazucker 2022-04-28 19:57:45

If we let y be the fifth number, then the ten integers are those from y − 4 to y + 5 inclusive, so we get

n = (y − 4) + (y − 3) + ⋯ + (y + 4) + (y + 5) = 10y + 5.

antonyouyang 2022-04-28 19:57:47

So maybe it's n=(a+0.5)*10

joshuazucker 2022-04-28 19:58:05

Right, or if we let the middle value be a + 0.5 or y + 0.5, then the total is ten times that value, or again 10y + 5.

joshuazucker 2022-04-28 19:58:19

Either way, we don't get a multiple of 10 because 10 is even!

joshuazucker 2022-04-28 19:58:29

We do get a multiple of 5, but not just any multiple of 5.

GarudS 2022-04-28 19:58:31

or n ≡ 5 (mod 10)

[Link] 12/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 19:58:52

We could say it that way. Or we could say that n is 5 times an odd integer, namely 2y + 1.

joshuazucker 2022-04-28 19:58:59

Finally, how about the condition with eleven integers?

hujenny2008 2022-04-28 19:59:23

n/11

lihao_david 2022-04-28 19:59:23

there's a middle this time, so it is just n/11

Andrew_Dou 2022-04-28 19:59:23

We have n = 11c

joshuazucker 2022-04-28 19:59:29

Yup! This is almost the same as with nine integers. Let's set z to be the median of the eleven integers. Then we get

n = (z − 5) + (z − 4) + ⋯ + (z + 4) + (z + 5) = 11z.

So n can be any multiple of 11.

joshuazucker 2022-04-28 19:59:33

We therefore seek the smallest positive integer that is:

(i) a multiple of 9,

(ii) odd,

(iii) a multiple of 5, and

(iv) a multiple of 11.

What is it?

hujenny2008 2022-04-28 20:00:05

495

MathHayden 2022-04-28 20:00:05

495

crestdino 2022-04-28 20:00:05

495

joshuazucker 2022-04-28 20:00:20

The smallest such integer is 5 ⋅ 9 ⋅ 11 = 495 .

joshuazucker 2022-04-28 20:00:40

The LCM of these numbers is just their product, and 99 is odd so we get the odd condition for free.

joshuazucker 2022-04-28 20:00:49

A set of consecutive positive integers beginning with 1 is written on a blackboard. One number is erased. The average (arithmetic
7
mean) of the remaining numbers is 35 17 . What number was erased?

joshuazucker 2022-04-28 20:01:07

Let's define some variables again.

joshuazucker 2022-04-28 20:01:14

Let n be the number of integers (and the last integer), and let x be the integer erased.

joshuazucker 2022-04-28 20:01:28

Can we get a rough idea about the value of either of these variables from the given average?

MatthewS192 2022-04-28 20:02:32

[Link] 13/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
n is maybe around say 70?

Ihatebar 2022-04-28 20:02:32

there should be around 70 or so integers?

andlind 2022-04-28 20:02:32

n is about 71

joshuazucker 2022-04-28 20:03:06

Yup, the average of 1 through 69 is 35, and erasing a number could make the average a little bigger or smaller depending on what
we erase, so maybe 68, 69, 70 are good guesses for n.

Bananaman27 2022-04-28 20:03:16

n is 1 more than a multiple of 17

MathHayden 2022-04-28 20:03:16

the value of n is close to 35 7/17 times 2 which is around 71, and is 1 more than a multiple of 17

MathHayden 2022-04-28 20:03:16

so it is probably 69

joshuazucker 2022-04-28 20:03:51

Right, when we erase one number (so we have n − 1 of them) and divide an integer (the total of the remaining numbers) by this (
n − 1), we get some number of seventeenths, so n − 1 must be a multiple of 17.

joshuazucker 2022-04-28 20:04:01

So the only reasonable value for n is 69.

joshuazucker 2022-04-28 20:04:21

If we want to be a little more precise about this, we can write down an equation stating the information about the average. What is
the sum of the numbers on the board after erasing x?

Andrew_Dou 2022-04-28 20:04:56

(n)(n + 1)/2 − x

lihao_david 2022-04-28 20:04:56

n(n+1)/2 - x

joshuazucker 2022-04-28 20:05:07

n(n+1)
The sum of the numbers was originally 1 + 2 + 3 + ⋯ + n = , so the sum of the numbers on the board after erasing x is
2
n(n+1)
− x.
2

joshuazucker 2022-04-28 20:05:12

How many numbers are on the board?

gladIasked 2022-04-28 20:05:37

n − 1

Andrew_Dou 2022-04-28 20:05:37

n − 1 now

A_MatheMagician 2022-04-28 20:05:37

n − 1

joshuazucker 2022-04-28 20:05:40

There are n − 1 numbers left. Therefore,

n(n+1)
− x 7
2
= 35 + .
n − 1 17

joshuazucker 2022-04-28 20:06:07

2
n n
The left side is roughly , or . So we can see n is about 70 from this equation too.
2n 2

[Link] 14/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:06:44

And again, we know n − 1 must be a multiple of 17 here, so we guess n = 69 .

joshuazucker 2022-04-28 20:07:11

Does n = 69 work? That is, if n = 69 can we get an integer value for x?

hujenny2008 2022-04-28 20:07:28

7

xixinyc 2022-04-28 20:07:28

yes

joshuazucker 2022-04-28 20:07:31

Sure, we can multiply both sides by 68 and rearrange to find x :

68 ⋅ 7
69 ⋅ 35 − x = 68 ⋅ 35 + ,
17

69 ⋅ 35 − 68 ⋅ 35 − x = 4 ⋅ 7,

35 − x = 28,

x = 7.

joshuazucker 2022-04-28 20:07:41

So, one possible answer is 7 .

Eric1219 2022-04-28 20:07:55

is there other solutions?

joshuazucker 2022-04-28 20:08:22

Let's make sure this is the only possible value for x. We can test based on the maximum and minimum possible values of x.

joshuazucker 2022-04-28 20:08:37

If we erase 1 from the board, we get

n(n + 1) − 2 (n − 1)(n + 2) n + 2
= = .
2(n − 1) 2(n − 1) 2

That's the largest possible average after erasing one number!

joshuazucker 2022-04-28 20:08:42

If we erase n from the board, we get

n(n + 1) − 2n n(n − 1) n
= = .
2(n − 1) 2(n − 1) 2

joshuazucker 2022-04-28 20:09:10

So we know that 35 17 must be between those values.
7

joshuazucker 2022-04-28 20:09:16

And n − 1 must be a multiple of 17.

joshuazucker 2022-04-28 20:09:21

So there are no other n that work.

joshuazucker 2022-04-28 20:10:02

We've seen a couple examples of this already, so let's put a big focus on

joshuazucker 2022-04-28 20:10:04

MAKING USE OF ALGEBRAIC FACTORIZATION

joshuazucker 2022-04-28 20:10:30

[Link] 15/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
For example, we've seen the very simple factorization of n = 10y + 5 = 5(2y + 1) as a way of seeing that n is an odd multiple
of 5.

joshuazucker 2022-04-28 20:10:37

Some problems involve algebraic expressions, particularly polynomials, in which the variables or the expression must represent an
integer. Sometimes we can solve such problems using the same kinds of algebraic factorizations that we typically apply to
standard algebra problems. The key to these problems is simply recognizing where we can work with the algebra to get us to a
point where we can apply our understanding of number theory.

joshuazucker 2022-04-28 20:10:53

Let's build some experience with a few examples of such problems.

joshuazucker 2022-04-28 20:11:00

Let f (x) = x
2
+ 3x + 2 and let S be the set of integers {0, 1, 2, … , 25}. Find the number of members s of S such that f (s)
has a remainder of 0 when divided by 6.

joshuazucker 2022-04-28 20:11:46

We could plug in a bunch of values, but as a hint toward a possibly easier method, there's the title of this section ...

MathHayden 2022-04-28 20:11:53

factor f(x): f(x)=(x+1)(x+2)

Andrew_Dou 2022-04-28 20:11:53

f (x) = (x + 2)(x + 1)

vanlucas 2022-04-28 20:11:53

2
x + 3x + 2 = (x + 1)(x + 2)

joshuazucker 2022-04-28 20:11:58

We can begin by factoring f (x) :

f (x) = (x + 1)(x + 2).

joshuazucker 2022-04-28 20:12:03

Now we want to determine when f (s) has a remainder of 0 when divided by 6. What does that mean? How can we test for that?

vanlucas 2022-04-28 20:12:30

2 and 3

joshuazucker 2022-04-28 20:12:45

Yeah! In number theory class, I'll very often say "When in doubt, prime factorize!"

joshuazucker 2022-04-28 20:12:58

If you want a number to be divisible by 6, that doesn't mean that its factors are divisible by 6.

joshuazucker 2022-04-28 20:13:17

For example 3 ⋅ 8 = 24 is divisible by 6 but neither 3 nor 8 are divisible by 6.

joshuazucker 2022-04-28 20:13:26

On the other hand, for primes we can say this!

joshuazucker 2022-04-28 20:13:43

If a product is divisible by 2 or 3 or any prime, then at least one of the factors is divisible by that prime.

gladIasked 2022-04-28 20:13:54

2&3

gladIasked 2022-04-28 20:13:54

It has to be a multiple of 2 and 3 because those are its factors

s214425 2022-04-28 20:13:54

it can be one is divisible by 2 and one is divisble by 3

[Link] 16/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:14:05

Exactly. We know f (s) needs to be divisible by 6. To be divisible by 6, an integer must be divisible by 2 and 3.

joshuazucker 2022-04-28 20:14:21

For which s do we know that f (s) is divisible by 2?

gladIasked 2022-04-28 20:14:41

all s

Andrew_Dou 2022-04-28 20:14:41

all integers s

Captain_Z 2022-04-28 20:14:41

all of them

joshuazucker 2022-04-28 20:14:44

Aha! Two consecutive integer factors! Either s + 1 or s + 2 must be even, which means that f (s) will always be even.

joshuazucker 2022-04-28 20:14:49

This examination of the evenness or oddness of the relevant integers is called a parity argument.

joshuazucker 2022-04-28 20:14:59

"Parity" is the fancy word for the evenness or oddness of a number.

joshuazucker 2022-04-28 20:15:08

You know, like 2 is the only even prime. That's really odd!

joshuazucker 2022-04-28 20:15:20

Our goal now is to find out exactly when f (s) will be a multiple of 3. When does that happen?

MathHayden 2022-04-28 20:16:10

all s except when s is a multiple of 3

GarudS 2022-04-28 20:16:10

when s is not a multiple of 3

Captain_Z 2022-04-28 20:16:10

when s isn't a multiple of 3

joshuazucker 2022-04-28 20:16:33

f (s) = (s + 1)(s + 2) will be a multiple of 3 when either s + 1 or s + 2 is a multiple of 3. This is the case whenever s is not a
multiple of 3.

joshuazucker 2022-04-28 20:16:48

So what is our answer?

joshuazucker 2022-04-28 20:17:30

Whoa, I'm seeing a lot of wrong answers here.

joshuazucker 2022-04-28 20:17:58

If you are having any issues counting a list of numbers, or maybe being off by one or whatever, make a list into something that
starts with 1 and counts by 1s.

joshuazucker 2022-04-28 20:18:33

So the number of integers in S , from 0 through 25, is the same as (adding 1 to each) the number in the list from 1 through 26, but
these are just counting, so there are 26 of them.

thrujet 2022-04-28 20:18:50

17

welxia88 2022-04-28 20:18:50

17

MathHayden 2022-04-28 20:18:50

26-9=17

[Link] 17/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:19:19

The multiples of 3 in S are

0, 3, 6, … , 24.

These are from 3 ⋅ 0 through 3 ⋅ 8, so there are 9 multiples of 3 in S , and that leaves 26 − 9 = 17 elements of S that are not
multiples of 3.

joshuazucker 2022-04-28 20:19:34

How many non-congruent rectangles are there whose sides are integers and whose perimeter (in units) is equal to their area (in
square units)?

hujenny2008 2022-04-28 20:20:12

set x and y as length and width

justJen 2022-04-28 20:20:12

write equations

lihao_david 2022-04-28 20:20:12

assign variables to sides

joshuazucker 2022-04-28 20:20:36

Suppose we call the side lengths m and n. (We often use letters from i through n to represent integers.)

Then, how can we rephrase the problem in terms of an equation?

antonyouyang 2022-04-28 20:20:58

So xy=2x+2y

kk626 2022-04-28 20:20:58

2(l+w)=lw

A_MatheMagician 2022-04-28 20:20:58

2x + 2y = xy

joshuazucker 2022-04-28 20:21:03

We want to know how many pairs of positive integers (m, n) satisfy the equation

2m + 2n = mn.

joshuazucker 2022-04-28 20:21:51

Usually one equation with two unknowns is a nightmare -- there are infinitely many solutions and they may not be too easy to
describe. Here we have a Diophantine equation, meaning that we are only examining the equation in terms of integer solutions.
This time it's even more specific -- positive integers! This gives a lot more hope that there are finitely many solutions.

joshuazucker 2022-04-28 20:21:53

How can we manipulate this equation?

vanlucas 2022-04-28 20:22:02

ssft

SIYQ 2022-04-28 20:22:02

simon's favorite factoring trick

Wihzj 2022-04-28 20:22:02

OMG is that Simon?

joshuazucker 2022-04-28 20:22:21

Yes! Simon Rubenstein-Salzedo says I should say hi to you all when this comes up.

joshuazucker 2022-04-28 20:22:26

And since Simon says so, well ...

[Link] 18/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:22:46

For those of you who haven't seen SFFT, also known as "completing the rectangle", it goes like this:

joshuazucker 2022-04-28 20:22:53

First we group everything on one side of the equation.

joshuazucker 2022-04-28 20:22:59

That gives

mn − 2m − 2n = 0.

joshuazucker 2022-04-28 20:23:10

Then, to "complete the rectangle", we add 4 to both sides.

Andrew_Dou 2022-04-28 20:23:22

(m − 2)(n − 2) = 4

larine 2022-04-28 20:23:22

(m-2)(n-2)=4

SIYQ 2022-04-28 20:23:22

(m-2)(n-2)=4

joshuazucker 2022-04-28 20:23:24

That makes it factorable:

mn − 2m − 2n + 4 = 4 ⟹ (m − 2)(n − 2) = 4.

joshuazucker 2022-04-28 20:23:50

It's like completing the square, but we have two different binomials, so it's a rectangle we're completing.

joshuazucker 2022-04-28 20:24:01

Around AoPS this is known as Simon's Favorite Factoring Trick or SFFT for short.

joshuazucker 2022-04-28 20:24:10

Our new equation is equivalent to the original equation. How can we count positive integer solutions?

gladIasked 2022-04-28 20:24:38

find factor pairs for 4

Captain_Z 2022-04-28 20:24:38

factors of 4

hujenny2008 2022-04-28 20:24:38

find factors of 4

joshuazucker 2022-04-28 20:25:00

Given that m and n are integers, we know that m − 2 and n − 2 are both integers. This tells us that we have the product of two
integers equal to 4.

euler12345 2022-04-28 20:25:11

The possible values for (m-2, n-2) are (1, 4), (2, 2), and (4, 1)

joshuazucker 2022-04-28 20:25:34

Yup. We have to be a little careful here: m and n are positive, sure, but that doesn't mean m − 2 and n − 2 are positive. They
could be 0 or negative!

joshuazucker 2022-04-28 20:25:57

However, they can only reach −1 and no further, and so if m − 2 are n − 2 are negative their product can't be more than 1.

joshuazucker 2022-04-28 20:26:08

[Link] 19/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
On the other hand, if our equation were instead (m − 3)(n − 3) = 4 , we would have a positive solution (m, n) = (1, 1) coming
from the negative factorization (−2)(−2) = 4 .

joshuazucker 2022-04-28 20:26:20

So, be careful about exactly which numbers in the problem can or can't be negative.

hujenny2008 2022-04-28 20:26:26

(6,3) and (4,4) so 2 solutions

wengyt96 2022-04-28 20:26:26

but (1,4) and (4,1) are congruent

antonyouyang 2022-04-28 20:26:26

Factor of 4 are 1,2, and 4, so it's (3,6), (4,4), and (6,3)

joshuazucker 2022-04-28 20:26:31

We see that (m, n) can be (3, 6), (6, 3), or (4, 4). So what is the answer to the problem? (Read the original problem carefully!)

joshuazucker 2022-04-28 20:26:39

(Always read the original problem one more time before answering.)

GarudS 2022-04-28 20:26:46

answer 2

MathHayden 2022-04-28 20:26:46

2

Andrew_Dou 2022-04-28 20:26:46

2

joshuazucker 2022-04-28 20:26:53

Since a 3 × 6 rectangle is congruent to a 6 × 3 rectangle, there are only 2 non-congruent rectangles with equal perimeter and
area.

joshuazucker 2022-04-28 20:27:02

The last couple of problems demonstrate a theme. Through algebraic factorization, we can reduce many number-theoretic
problems to integer factorization, which is easy (well, it's easy for smallish integers, anyway).

joshuazucker 2022-04-28 20:27:50

And you can use integer factorizations to help you find algebraic ones, too.

joshuazucker 2022-04-28 20:28:02

For example, should you ever get stuck wondering whether x3 + 1 has a factorization (or trying to remember what it is), it's not
such a bad idea to make a table of integer values and their factorizations:

joshuazucker 2022-04-28 20:28:04

3
n n + 1 prime factorization

1 2 2

2
2 9 3

2
3 28 2 ⋅ 7

4 65 5 ⋅ 13

2
5 126 2 ⋅ 3 ⋅ 7

6 217 7 ⋅ 31

3
7 344 2 ⋅ 43

joshuazucker 2022-04-28 20:28:31

Maybe you can see a factor of 2, 3, 4, 5, 6, … and so you see that n + 1 is always a factor, and then you can figure out what the
other factor has to be.

joshuazucker 2022-04-28 20:28:40

[Link] 20/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

On the other hand, compare this table for n 4

+ 1 :

joshuazucker 2022-04-28 20:28:41

4
n n + 1 prime factorization

1 2 2

2 17 17

3 82 2 ⋅ 41

4 257 257

5 626 2 ⋅ 313

joshuazucker 2022-04-28 20:29:00

Some of these are prime! So unless there's some weird algebraic piece that keeps being prime for some reason, there can't be a
nice integer factorization.

joshuazucker 2022-04-28 20:29:06

(In fact, it has a not-so-nice factorization:

2 2
(n − n√2 + 1) ⋅ (n + n√2 + 1),

but there is no factorization with integer or even rational coefficients.)

joshuazucker 2022-04-28 20:29:38

(This factorization comes from a nice version of completing the square: add and subtract 2n2 and then factor as difference of
squares.)

joshuazucker 2022-04-28 20:29:48

If n consecutive positive integers add up to 784, what is the smallest possible value of n that is greater than 1?

joshuazucker 2022-04-28 20:30:05

We could just go hunting for a solution -- and eventually we would find it. But you never know how much labor that might take.

joshuazucker 2022-04-28 20:30:07

How can we convert this problem into algebra?

MathHayden 2022-04-28 20:30:48

try using the median again

Andrew_Dou 2022-04-28 20:30:48

let the first integer be x

lihao_david 2022-04-28 20:30:48

assign a variable to the middle/beginning number

joshuazucker 2022-04-28 20:30:56

Yeah, we could go either way here.

joshuazucker 2022-04-28 20:31:08

I'll call the first term a because we often seem to label sequences with a for the first term.

joshuazucker 2022-04-28 20:31:16

And we'll let n be as defined in the problem.

joshuazucker 2022-04-28 20:31:27

So, what is the sum of n integers beginning with a, in terms of a and n?

joshuazucker 2022-04-28 20:32:51

Think carefully about what the last number in the list will be! A lot of you are off by 1 in the same way as a lot of you were off by 1
in the 0 through 25 counting, or the multiples of 3 from 0 through 24, in that previous problem.

MathHayden 2022-04-28 20:33:41

[Link] 21/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
a+(a+1)+...+(a+n-1)=na+(n-1)(n)/2

lihao_david 2022-04-28 20:33:41

(2a+n-1)n/2

wengyt96 2022-04-28 20:33:41

n/2*(2a+n-1)?

joshuazucker 2022-04-28 20:33:50

Yeah! There's a bunch of ways to think about this.

joshuazucker 2022-04-28 20:33:59

IMPORTANT: The last term is a + n − 1. (Not a + n! Make sure you avoid this common error!)

joshuazucker 2022-04-28 20:34:32

I think I'm seeing three different methods here.

joshuazucker 2022-04-28 20:34:47

My method for arithmetic series like this is "total = average * how many".

joshuazucker 2022-04-28 20:34:51

There are n numbers, that's given.

joshuazucker 2022-04-28 20:35:05

We have an arithmetic progression, so the average of terms is the average of the first and last terms:

a + (a + n − 1) n − 1
= a + .
2 2

joshuazucker 2022-04-28 20:36:02

Then the sum is the average times the number of terms, so

n − 1
n (a + ) = 784.
2

joshuazucker 2022-04-28 20:36:28

I see some of you thinking about the sum of (a + 0) + (a + 1) + … + (a + (n − 1)).

joshuazucker 2022-04-28 20:36:46

n(n − 1)
That's cool! We have n copies of a, plus the sum from 0 through n − 1 which is .
2

joshuazucker 2022-04-28 20:37:38

n(n − 1)
So that gives an + , which is the same as my formula after distributing n.
2

joshuazucker 2022-04-28 20:37:39

Here's another clever way: The sum we want is the sum of the first a + n − 1 natural numbers minus the sum of the first a − 1
natural numbers:

(a + n − 1)(a + n) a(a − 1) n(2a + n − 1)

− = .
2 2 2

joshuazucker 2022-04-28 20:38:04

Using this equation, how can we find the smallest possible value of n?

joshuazucker 2022-04-28 20:38:38

n − 1
Remember, n is not necessarily a divisor of 784 because the stuff in parentheses, a + is not necessarily an integer.
2

[Link] 22/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:38:50

If we want to use divisibility, let's multiply both sides by 2 to eliminate fractions.

joshuazucker 2022-04-28 20:39:02

That gives us

n(2a + n − 1) = 1568.

joshuazucker 2022-04-28 20:39:34

Now n has to be a factor of 1568, and if n is odd then the other factor 2a + n − 1 has to be even, and vice-versa.

joshuazucker 2022-04-28 20:39:56

So we can't use 2 ⋅ 784 as a factorization, for example, because both are even in that case.

MatthewS192 2022-04-28 20:40:13

5 2
1568 = 2 ⋅ 7

joshuazucker 2022-04-28 20:40:19

We could begin with a prime factorization: 1568 = 2
5
⋅ 7 .
2

A_MatheMagician 2022-04-28 20:40:30

is it 7

andlind 2022-04-28 20:40:32

I think it is 7

joshuazucker 2022-04-28 20:40:55

Yes, either n is odd times some even factor, in which case n is 7 or 49 ...

joshuazucker 2022-04-28 20:41:36

or n is even times some odd factor, in which case n is 2 or 2 or maybe the whole 1568 (although that will require a bunch of
5 5
⋅ 7

negative integers in the sum too!)

joshuazucker 2022-04-28 20:41:41

So the smallest is ...

xixinyc 2022-04-28 20:41:44

7

Andrew_Dou 2022-04-28 20:41:44

testing n = 7 works and 7 is obviously less than 49

joshuazucker 2022-04-28 20:41:53

Yes: if we plug in n = 7 to our original equation, we get

7(2a + 7 − 1) = 1568 ⟺ 2a + 6 = 224,

which has a positive integer solution a = 109.

joshuazucker 2022-04-28 20:42:01

We do need to check that all the integers are positive!

joshuazucker 2022-04-28 20:42:08

In particular, this gives us the sequence 109, 110, 111, 112, 113, 114, 115, which shows n = 7 is indeed our answer.

joshuazucker 2022-04-28 20:42:16

Let x and y be two-digit integers such that y is obtained by reversing the digits of x. The integers x and y satisfy

2 2 2
x − y = m

for some positive integer m. What is x + y + m?

[Link] 23/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:42:34

Ugh, digit reversing. Well, that means it's hard to describe the relationship between x and y directly.

joshuazucker 2022-04-28 20:42:48

Thankfully, they are given to be two digit integers. What would be a good way to use algebra to help us out?

hujenny2008 2022-04-28 20:42:58

set x=10a+b and y+10b+a

Andrew_Dou 2022-04-28 20:42:58

we could define x = 10a + b so y = 10b + a?

rsun 2022-04-28 20:42:58

we can write x as 10a + b, and y as 10b + a

joshuazucker 2022-04-28 20:43:05

Letting x = 10a + b and y = 10b + a for digits a and b we have

2 2 2 2 2 2
x − y = m ⟹ (10a + b) − (10b + a) = m .

joshuazucker 2022-04-28 20:43:30

(It might be useful to write down that since these are both two-digit integers, we have a and b nonzero, so they are digits 1 through
9 only.)

euler12345 2022-04-28 20:43:43

Factor the difference of squares?

andlind 2022-04-28 20:43:43

difference of squares

hujenny2008 2022-04-28 20:43:43

difference of squares

joshuazucker 2022-04-28 20:43:45

We can factor the left side as a difference of squares:

2 2
(10a + b) − (10b + a) = ((10a + b) + (10b + a))((10a + b) − (10b + a))

= (11a + 11b)(9a − 9b)

= 99(a + b)(a − b).

So our equation becomes

2
99(a + b)(a − b) = m .

joshuazucker 2022-04-28 20:44:20

Hmmm, m2 is an integer and a multiple of 99. What can we conclude about m itself?

lihao_david 2022-04-28 20:44:49

it is a multiple of 3 and 11

Eric1219 2022-04-28 20:44:49

multiple of 33

joshuazucker 2022-04-28 20:44:51

Since m2 is a multiple of 3 ⋅ 3 ⋅ 11, we know that m must be a multiple of 3 ⋅ 11 = 33.

joshuazucker 2022-04-28 20:44:58

We can get the other factor of 3 from the squaring!

[Link] 24/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:45:11

How can we express "m is a multiple of 33" in a useful algebraic way?

lihao_david 2022-04-28 20:46:03

m = 33n

anushkahalder 2022-04-28 20:46:03

m = 33n if n is some iteger

vanlucas 2022-04-28 20:46:03

M = 33n

joshuazucker 2022-04-28 20:46:24

We can now let m = 33k for some integer k and rewrite our equation:

2 2
99(a + b)(a − b) = 33 k .

Dividing both sides by 99 gives

2
(a + b)(a − b) = 11k .

joshuazucker 2022-04-28 20:46:40

And now what divisibility statements can we make?

joshuazucker 2022-04-28 20:46:54

When we're working with equations involving integers, we can often make useful observations about divisibility.

Andrew_Dou 2022-04-28 20:47:00

(a+b)(a-b) is divisible by 11

joshuazucker 2022-04-28 20:47:05

And 11 is prime so

Captain_Z 2022-04-28 20:47:07

either a+b or a-b have to be divisible by 11

joshuazucker 2022-04-28 20:47:16

And a and b are single digits 1 through 9, so

hujenny2008 2022-04-28 20:47:21

a+b has to be 11 and a-b has to be a perfect square

rsun 2022-04-28 20:47:21

a + b = 11 , since a − b cannot equal 11

joshuazucker 2022-04-28 20:48:01

Right, dividing both sides by a + b = 11 (since a + b can't be 22 or any larger multiple of 11), we get

2
a − b = k .

joshuazucker 2022-04-28 20:48:09

What now?

wengyt96 2022-04-28 20:48:23

a-b either = 1 or =4

joshuazucker 2022-04-28 20:48:34

Yeah, and since a + b = 11 we know one of them is odd and one is even.

joshuazucker 2022-04-28 20:48:37

There's parity again!

[Link] 25/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

joshuazucker 2022-04-28 20:48:46

You can see how much the same tools keep being useful again and again and again.

MathHayden 2022-04-28 20:48:52

a-b is always odd

andlind 2022-04-28 20:48:59

a-b = 1

andlind 2022-04-28 20:49:08

a=6b=5

joshuazucker 2022-04-28 20:49:09

When a + b and a − b we have a and b
2
= 11 = 1 = 1, = 6 = 5.

joshuazucker 2022-04-28 20:49:23

We now see that x = 10a + b = 65 and y = 10b + a = 56. This tells us that

2 2 2 2 2
x − y = 65 − 56 = (65 + 56)(65 − 56) = 121 ⋅ 9 = m .

Thus m = 33 .

GarudS 2022-04-28 20:49:32

ANS 154

Lucasfunnyface 2022-04-28 20:49:32

33 + 65 + 56 =154

joshuazucker 2022-04-28 20:49:39

Our final answer is

x + y + m = 65 + 56 + 33 = 154.

joshuazucker 2022-04-28 20:50:52

Let xn be the remainder when x is divided by n. Compute the sum of all positive integers x that satisfy

5 5 6 6
x (x5 ) − x − (x5 ) + x (x5 ) = 0.

joshuazucker 2022-04-28 20:51:05

The notation in this problem is confusing to the eye, but it's important that we recognize that what it stands for isn't confusing. The
remainder when x is divided by 5 is a pretty simple concept!

joshuazucker 2022-04-28 20:51:23

Since x5 looks too much like x to me, let's replace x5 with the less confusing symbol y. Then our equation becomes

5 5 6 6
x y − x − y + xy = 0.

joshuazucker 2022-04-28 20:51:40

Now the symmetry between x and y is more visible: if we swap them, the equation stays the same.

joshuazucker 2022-04-28 20:51:53

That gives some hints about how to factor the left side, maybe?

joshuazucker 2022-04-28 20:52:02

Or maybe you can just see the factoring by grouping right away?

joshuazucker 2022-04-28 20:52:10

Either way ... what is the factorization of the left side?

[Link] 26/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory

Andrew_Dou 2022-04-28 20:52:34

5 5
(x − y)(y − x) = 0

rsun 2022-04-28 20:52:34

5 5
(x − y)(y − x)

Captain_Z 2022-04-28 20:52:34

(x^5-y)(y^5-x)=0

joshuazucker 2022-04-28 20:52:38

We have the factorization

5 5
(x − y)(y − x) = 0.

Andrew_Dou 2022-04-28 20:53:00

so either x5 = y or y 5 = x

joshuazucker 2022-04-28 20:53:02

And just like in Introduction to Algebra, if a product is zero then one or the other of the factors must be zero.

joshuazucker 2022-04-28 20:53:05

We now see that either y 5 = x or x5 = y.

joshuazucker 2022-04-28 20:53:10

Wait! Does that mean there are infinitely many solutions, since we could let y be any positive integer and x = y
5
? That would be a
problem, since we're supposed to add up all the possible values of x...

Andrew_Dou 2022-04-28 20:53:51

no... y = 0, 1, 2, 3, 4

euler12345 2022-04-28 20:53:51

y is the remainder when x is divided by 5!

MathHayden 2022-04-28 20:53:51

no because y is limited to 0,1,2,3,4

joshuazucker 2022-04-28 20:53:54

Oh right, remember that y must be the remainder when x is divided by 5. So y can only be 0, 1, 2, 3, or 4.

joshuazucker 2022-04-28 20:53:58

And in fact y cannot be 0, since then x would be 0, but we are given that x is positive.

joshuazucker 2022-04-28 20:54:45

The only solution (for positive x) to x is x ; otherwise y would be too big. But y yields
5 5
= y = 1 = x

5
1 = 1,
5
2 = 32,
5
3 = 243,
5
4 = 1024.

joshuazucker 2022-04-28 20:54:53

These are all of the possibilities, but before we sum them up, what do we need to check for each one?

hujenny2008 2022-04-28 20:55:30

the remainder when divided by 5

Eric1219 2022-04-28 20:55:30

mod 5

joshuazucker 2022-04-28 20:55:44

[Link] 27/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
Remember that we set y to be the remainder that x leaves when divided by 5. Looking at the last digits, we can see that this is
true.

joshuazucker 2022-04-28 20:55:51

If you know Fermat's Little theorem which says that a5 and a leave the same remainder when divided by 5, you probably checked
this very quickly. If you don't know it, not to worry; we'll be covering it later in this course.

hujenny2008 2022-04-28 20:55:55

1300

joshuazucker 2022-04-28 20:56:06

Since all four solutions work, the sum is 1 + 32 + 243 + 1024 = 1300.

joshuazucker 2022-04-28 20:56:19

SUMMARY

joshuazucker 2022-04-28 20:56:27

We didn't learn anything fancy today. This was the beginning of our exploration of the ways in which we can use algebraic concepts
in number-theoretic problems. Ultimately, all the familiar processes of solving equations (including systems of equations), such as
factoring algebraic expressions, expanding binomials, etc., can be used alongside our familiar number theory tools to solve a far
greater array of problems.

joshuazucker 2022-04-28 20:57:03

Those familiar number theory tools include parity, and using algebraic representations like n = k
2
to show that n is a square, or
n = 11k to show that n is a multiple of 11.

joshuazucker 2022-04-28 20:57:07

Just like a firm foundation in algebra is important when you start studying subjects like calculus, more difficult number theory
concepts and problems also require a firm grasp of how to use algebra together with the tools of number theory.

joshuazucker 2022-04-28 20:57:32

Now, I'd like to talk a little bit more about what you should do between classes.

joshuazucker 2022-04-28 20:57:35

First, if you haven't been to the course homepage yet, check it out right after class. You can get to it by clicking "My Classes" on the
top right of any page on the AoPS website when you're logged in.

joshuazucker 2022-04-28 20:57:45

Or, go to [Link]

joshuazucker 2022-04-28 20:58:09

The course homepage has 4 tabs: "Overview", "Homework", "Message Board", and "Report". Here's what each one is about:

joshuazucker 2022-04-28 20:58:15

Overview
This tab includes a Course Introduction document, which you should read once, and also the syllabus for the course. Also, within
an hour or two after every class, we'll post a transcript of everything that happened here. You can use this to review anything from
class that you might not have understood at the time.

joshuazucker 2022-04-28 20:58:29

Homework
This tab will include a few problems to solve between classes each week. Some of these can be answered with just a number.
Other problems will ask you to write an explanation of your work. Learning to explain your thinking is just as important as learning
to think well in the first place! On the writing problems, you'll get written feedback from an AoPS grader, and your score will be
based on the content as well as the style of your writing.

joshuazucker 2022-04-28 20:58:54

In my opinion, this feedback on your writing is one of the most valuable parts of the online course. Take the time to write well and
to learn from the feedback to improve your writing.

joshuazucker 2022-04-28 20:59:03

Message Board
The message board is where you can chat with the instructor and with other students during the week. Additionally, we have Office

[Link] 28/29
5/4/22, 6:20 PM 3085 Intermediate Number Theory
Hours on the message board: an AoPS staff member will be on the message board to answer questions in real time every day from
4:00 - 5:30 PM ET (1:00 - 2:30 PM PT) and 7:30-8:30 PM ET (4:30-5:30 PM PT).

joshuazucker 2022-04-28 20:59:08

We will post extra discussion questions after class each week that will give you all something to talk about!

joshuazucker 2022-04-28 20:59:17

We have integrated the message board into the transcripts and homework to make it easier to discuss the transcript and the
homework -- even specific lines in the transcript or problems in the homework. If you see a speech balloon icon, clicking it will
show you the threads already discussing that item.

joshuazucker 2022-04-28 20:59:24

Clicking a pencil and paper icon V will create a new thread linked to that item. A linked thread will make it easier for everyone to
see exactly what you want to discuss.

joshuazucker 2022-04-28 20:59:32

Whenever you create a new thread, it will also e-mail the instructors and assistants to let them know that a question has been
asked. Also you have the option to ask questions that are anonymous to the other students (though you needn't ever be
embarrassed to ask a question!).

joshuazucker 2022-04-28 21:00:11

You can also get to the course message board by clicking on the Message Board tab of the class homepage.

joshuazucker 2022-04-28 21:00:19

Report
This tab will tell you how you're doing in this course. It has magic bars that track your performance on the weekly Challenge
Problems and in class. Green bars mean that you've passed the task and can move on. Blue bars mean you've mastered the task.
Red and orange mean "Keep going!"

joshuazucker 2022-04-28 21:00:37

Throughout the course, you should visit the class homepage at least a couple of times a week, and use the Homework tab to make
sure you're keeping up with your work.

joshuazucker 2022-04-28 21:00:45

There's also a My Goals tab I forgot to mention.

joshuazucker 2022-04-28 21:01:12

It gives a suggested schedule for the week to help you stay on track.

joshuazucker 2022-04-28 21:01:58

That's it for class tonight. Are there any questions?

© 2022 Art of Problem Solving

About Us • Contact Us • Terms • Privacy

Copyright © 2022 Art of Problem Solving

[Link] 29/29