Question

How can I prove that a set of p=3q+5r where q and r are integers equals or contains the whole set of integers?

Answer 1

Heyy

Answer 2

hiya

Answer 3

First lets look at construction based proof. This is not so elegant, but this is a bit easy to comprehend...

Answer 4

Can you find \(q, r\) that satisfy below equation ?
\[1 = 3q+5r\]

Answer 5

q=7 r=(-4)

Answer 6

Excellent!

\[1 = 3(7) + 5(-4)\]

Answer 7

Multiply \(p\) through out, the equation becomes :

\[p = 3(7p) + 5(-4p)\]

Answer 8

Notice that for any integer left hand side \(p\), we have :

\(q = 7p\)
\(r = -4p\)

Answer 9

That ends the proof because, by constructing, we have showed that there exist \(q,r\) for any given \(p\) that satisfy the equation \(p = 3q+5r\).

Answer 10

I see, thanks for the answer. On a side not, would there be any significance or utility of the 7p and -4p?. Looks like something could be done using linear algebra.

Answer 11

nvm that I just realized how strange a question that was =) thanks again

Answer 12

I think so... I too don't like these construction based proofs..
Lets try proving this in another way maybe

Answer 13

do you have any ideas using linear algebra ?

Answer 14

not really, but I can give some context for the original question (it may give you a clue). I just started learning from the book Fundamental Concepts of Mathematics and I'm on the 1 section called Set Notation. Among the exercise questions was this one which was starred and no answer was given(attached). So the context is subsets etc. and the like. No linear algebra etc. was studied yet as this is the first Unit.

Answer 15

I'm a chem E. grad but I'm extremely rusty on anything maths related other than differentials and calculus. I just started learning maths as a hobby yay :D

Answer 16

Awesome! This is more like number theory...
I think the author wants you prove it using divisibility arguments..

Answer 17

Notice that \(\gcd(6,10)=2\)

Answer 18

I mean the way I asked the question here is where I had already reformed it into 2*(3q+5r). I though if I could prove 3q+5r is equal to Z, then it should be okay

Answer 19

Essentially, the problem is equivalent to proving below statement :

Any "linear combination of two given integers" is a multiple of the "gcd of the two integers".

Answer 20

Interesting perspective but I'm not used to the ways of Maths. so I don't know where to take it =)