Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-02-24 21:53:32

mrpace
Member
Registered: 2012-08-16
Posts: 88

Help with a fairly simple proof please?

Show that 5n+3 and 7n+4 are relatively prime for all n.

I'm fairly new at proofs and I think I've made decent inroads but can't seem to finish it elegantly.

Here is my attempt:

Show that gcd (5n+3 , 7n+4) = 1

let A=5n+3 and B=7n+4

if n is even then A is odd. If n is odd then B is odd. Therefore gcd cannot be even.

For an odd number (k) to divide A as well as B, the difference between A and B must be some multiple of k which can only be true if k equals 1.

That last line I don't think is sufficient but I don't know how to put it in more convincing terms. Help is appreciated.

Offline

#2 2015-02-24 22:09:51

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: Help with a fairly simple proof please?

Use the Euclidean algorithm.

Offline

#3 2015-02-25 01:09:46

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Help with a fairly simple proof please?

Two integers
are relatively prime if and only if there exist integers
such that
.

Now,
. So try and find
such that

[list=*]
[*]

[/*]
[/list]


Bassaricyon neblina

Offline

#4 2015-02-25 08:55:15

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Help with a fairly simple proof please?

The two polynomials 5n+3 , 7n+4 are already factored and obviously have no common factor.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2015-02-25 11:39:08

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Help with a fairly simple proof please?

bobbym wrote:

The two polynomials 5n+3 , 7n+4 are already factored and obviously have no common factor.

They are not polynomials, they are numbers.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#6 2015-02-25 20:06:59

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Help with a fairly simple proof please?

If the gcd of the polynomials is one does that not mean for all n too?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2015-02-25 21:33:42

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Help with a fairly simple proof please?

No. Try n and n+2 for n even.


Bassaricyon neblina

Offline

#8 2015-02-26 00:03:33

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Help with a fairly simple proof please?

I'd be grateful for any comments about the validity of this:

Say 7n+4 and 5n+ 3 have a common divisor, d.

Then the result of subtracting the smaller from the larger must also be divisible by d.

So 5n + 3 and 2n + 1 must be divisible by d.

Continuing

3n + 2 and 2n + 1 must be divisible by d.

And again

2n + 1 and n + 1 must be divisible by d.

And, one last time

n+ 1 and n must be divisible by d.

Only d = 1 is therefore possible.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#9 2015-02-26 00:08:23

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Help with a fairly simple proof please?

Hej Bob

That is correct. (Det är rätt.)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#10 2015-02-26 00:13:24

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Help with a fairly simple proof please?

Yes, that works fine. It's along the lines of what zetafunc suggested in post #2. up


Bassaricyon neblina

Offline

#11 2015-02-26 00:19:49

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Help with a fairly simple proof please?

Oh, thanks.  No one is more surprised than me.  And I'd like to say that I don't know what the Euclidean algorithm is (my failure to bother to learn such things is legendary smile ) so I claim double credit for thinking it up myself.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

Board footer

Powered by FluxBB