Linked Questions

1
vote
2answers
183 views

Natural numbers and linear combinations [duplicate]

Prove that every natural number $n\geqslant 12$ can be written as a linear combination of $4$ and $5$ with non negative integer coefficients. I proceeded by induction. For $n=12$ we have $12=3\cdot ...
2
votes
0answers
78 views

basic number theory question (gcd) [duplicate]

Possible Duplicate: Largest integer that can’t be represented as a non-negative linear combination of $m, n = mn - m - n$? Why? Q: Suppose $u$ and $v$ are positive integers, and $k$ a number such ...
0
votes
0answers
38 views

A positive Bézout's identity [duplicate]

Question: Is the following statement true? Statement: Let $a, b \ge 1$ be coprime numbers. Then $\exists N \ge 0 $ $\forall n \ge N$ $\exists u, v \ge 0$ with $n=au+bv$. Let $N(a,b)$ be the ...
0
votes
0answers
12 views

If $S=\{ax+by: x,y\in \mathbb{Z^+} \}$ then $ab-a-b$ is the maximum element in $\mathbb{N} \setminus S$. [duplicate]

Let $a,b$ be positive relatively prime integers and $S$ be a set defined by $\{ax+by: x,y\in \mathbb{Z^+} \}$. I want to show that $ab-a-b$ is the maximum element in $\mathbb{N} \setminus S$. We ...
8
votes
3answers
947 views

When do the multiples of two primes span all large enough natural numbers?

It is well-known that given two primes $p$ and $q$, $pZ + qZ = Z$ where $Z$ stands for all integers. It seems to me that the set of natural number multiples, i.e. $pN + qN$ also span all natural ...
3
votes
2answers
2k views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
2
votes
3answers
332 views

Conjecture about linear diophantine equations

I've been dabbling with linear Diophantine equations and came across a rather interesting pattern that I would like to conjecture as true but I have no idea how about to come up with a proof. Let $ax+...
2
votes
1answer
313 views

Every $n > 17$ is a non-negative integer combination of $4$ and $7$. [duplicate]

Prove that every integer greater than $17$ is a non-negative integer combination of $4$ and $7$. In other words, for all natural numbers $n$, $n$ greater or equal to $17$, there exists non-negative ...
3
votes
1answer
170 views

Does this group action fix a point?

I saw a question on a forum earlier, and I'm curious to see how it can be solved. Suppose that $G$ is a group of order $pr$ for distinct primes $p$ and $r$, and let $G$ act on a set $S$ of order $pr-...
0
votes
3answers
212 views

solving a linear Diophantine equation

How to show that there exist non-negative integers $x,y$ such that $ax+by=ab+k$ where $a,b$ are co-prime whole numbers is true for all non zero integers $k$. PS: Sorry for missing the key ...
3
votes
1answer
416 views

Existence of Natural Solutions to Linear Diophantine Equation [duplicate]

If you have a Linear Diophantine Equation, $ax + by = c$, such that $a, b, c$ are constants is there an efficient way to check that there exists some pair $X, Y \in \mathbb N$? I recognize that I ...
1
vote
2answers
192 views

Largest integer which cannot be made with 5x + 7y where x and y are integers

What is the largest positive integer $n_0$ for which there are no $x, y ∈ \mathbb{Z}$ with $x, y ≥ 0$ so that $n_0 = 5x + 7y$? Give a proof that if $n > n_0$ then there are non-negative integers $...
-2
votes
2answers
126 views

Prove that any postage greater than 17 can be made using 4 and 7 cent stamps

Please use strong induction for the problem. I know that regular induction doesn't work. I assume there is a proof by logic by simply saying that 18, 19 and 20 cents can be made using these stamps and ...
0
votes
1answer
73 views

For coprime $p$ and $q$, what is the largest number $m$ that can not be written as $ap+bq$ for $a,b \geq 0$.

This is a sub-problem that I am solving in light of a larger more general problem. I believe it is probably quite easy but I often struggle with number theory. Here is my theorem: the number $m$ is ...