You are not logged in.
Pages: 1
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
[list=*]
[*]
Bassaricyon neblina
Offline
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
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
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
No. Try n and n+2 for n even.
Bassaricyon neblina
Offline
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
Offline
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
Yes, that works fine. It's along the lines of what zetafunc suggested in post #2.
Bassaricyon neblina
Offline
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 ) 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
Offline
Pages: 1