Number Theory

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Number Theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Archimedes Junior 2010

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1391 posts

#1 h Mar 17, 2020, 7:34 AM • 1 Y

Y by cubres

Determine the number of all positive integers which cannot be written in the form $80k + 3m$ , where $k,m \in N = \{0,1,2,...,\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EmirhanYagcioglu

88 posts

EmirhanYagcioglu

#2 h Mar 17, 2020, 8:54 AM • 2 Y

Y by Hexagon_6-, cubres

Say $x$ is a good number if there are some $k,m\in\mathbb N$ such that $80k+3m=x$ , if otherwise say $x$ is a bad number. We are looking for bad numbers.

This is a known result that all numbers greater than $ab-a-b$ for $a,b\in\mathbb N$ can be written in the form $ax+by$ for $x,y\in\mathbb N$ . So in this question, we can quickly say all numbers greater than $157$ are good numbers, only thing we must look for is the numbers less than $158$ .

Let $80k+3m=x$ . We are looking for the case where $x\leq157$ .

When $k=0$ , $3m=x$ so if $3\mid x$ , then $x$ is good.
When $k=1$ , $3m=x-80$ so $3\mid x+1$ for $80\geq x$ is also good. This means If $80\leq x\leq157$ and $x\equiv1\mod3$ , then $x$ is bad. So the set of all bad numbers $E$ is the following:
$E=A\cup B, A=\{x: x\equiv1\mod3, 80\leq x\leq157\}=\{82,85,\cdots ,157\}, B=\{x: x\equiv 1,2\mod3, 0\leq x <80\}=\{1,4,\cdots,79\}\cup \{2,5,\cdots 77\}$ which has $79$ elements at total.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#3 h Apr 17, 2025, 1:25 AM • 1 Y

Y by cubres

This is a very late addendum, but as EmirhanYagcioglu indicated in his fine solution, there is a general result, probably due to James Joseph Sylvester, which solves this problem which is often referred to as Frobenius' coin problem. The result says that, if $a$ and $b$ are relatively prime positive integers, the largest positive integer which can not be written in the form $ka + mb$ with $k, m \in \mathbb{N}_0$ is the number $ab-a-b$ . But there is an addendum to that result which says that, of all the numbers from 0 to $ab-a-b$ , exactly half of them cannot be written in such a way.

So, altogether, there are exactly $\tfrac{1}{2} (ab-a-b+1)$ positive integers which cannot be written in that form. In our case with $a=80$ and $b=3$ this amounts to 79 numbers. But, of course, EmirhanYagcioglu's solution above is absolutely worthwhile and can very probably be generalized to attain this general remark.

This ends my addendum about an addendum.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a