Question

Prove that numbers 5n + 1 and 6n + 1 are coprime between each other, when n is natural number.

Answer 1

That's how I would do it:
if both of them aren't coprime, then their GCD would be more than 1. And their difference would be divisible by that as well:
5n + 1 = k * A
6n + 1 = k * B
(6n + 1) - (5n + 1) = k(B - A)
n = k(B - A)
n/(B - A) = k

However, I think it's not really sufficient to prove that k could only be 1... What else would I need to do?

Answer 2

A and B should be natural numbers as well.

Answer 3

However, it's only my guess, so if anybody has any ideas, please share them ;)

Answer 4

Are you really convinced that the gcd of 'a' and 'b' is same as the gcd of 'a' and 'a-b' ?

Answer 5

Yeah, exactly, and you can keep going with it too, so what you did was show:

\[\gcd(6n+1,5n+1) = \gcd(n,5n+1)\]
but you can now subtract n from 5n+1 in the same way. We can just go ahead and repeat that step 5 times to get:

\[\gcd(n,5n+1) = \gcd(n,1) = 1\]
At this point you're pretty much there, the greatest common divisor of 1 with any number can really only be 1. In other words relatively prime.

Answer 6

Ehh, somehow I can't really understand why what @Kainui said works... Could anyone explain? ;)

Answer 7

@ganeshie8 I am not convinced. I am just convinced that gcd of 6n + 1 and 5n + 1 is k.

Answer 8

Yes, it shouldn't be obvious if you're seeing it for the first time today
It took me a couple of weeks to fully understand this result. This is also called Euclid gcd algorithm. I'd love to explain, one moment.

Answer 9

Maybe let's start with a simple problem :

Suppose you have two logs of lengths 12 and 15. You want to cut them into pieces of equal lengths.
What's the maximum possible length of each piece ?

Answer 10

so, gcd(12, 15) = 3
so, cutting 4 pieces of 3 length and 5 pieces of 3 length from another log.

Answer 11

Yes. May i know how you figured out the GCD ?

Answer 12

12 = 3 * 2^2
15 = 3 * 5

Answer 13

The only number that is in both of the lengths is 3.

Answer 14

Nice. Suppose you didn't have a measuring tape. You need to cut them using only saw. How would you do that ?

Answer 15

"I am just convinced that gcd of 6n + 1 and 5n + 1 is k."

So looking at your argument here:

5n + 1 = k * A
6n + 1 = k * B
(6n + 1) - (5n + 1) = k*(B - A)
n = k*(B - A)

Let's make it look more consistent and just relabel C = (B-A) so that we have:

5n + 1 = k * A
6n + 1 = k * B
n = k * C

All of these numbers have the exact same gcd, which is the value k. Before we just had A and B, but now we have C which is less than A and B. So we can do this sorta tricky business. We can instead look at the gcd of the two smallest values in that list of 3 numbers, and because they all have the same gcd=k, we don't have to worry.

I have also had EXTREME troubles with this too, I am pretty sure @ganeshie8 has seen me struggle many times in the past lol.

Answer 16

I left out the most important step, we basically can repeat the exact same process except now we choose 5n+1 and n since those are the smallest instead of using 6n+1 and 5n+1. So we are basically starting the whole process over again if that makes sense.

Answer 17

I would take 15 log and place it near 12 log, 15 - 12 = 3. So, I would get a log with length of 3 and then I would cut all wood using the first 3 log as example.

Answer 18

Brilliant!
So you do see how/why the Euclid gcd algorithm works ?

Answer 19

@Kainui Oh! That clears up some things! Thanks! (Not sure to who give the medal, because both you and @ganeshie8 are big help right now ;) )

Answer 20

@ganeshie8 Yes! :) It's amazing that you were able to use such a simple example. :) Thank you very much!

Answer 21

Awesome :)
Pls medal kai. I'm on mobile atm.. I'll give you medal once I login to my computer

Answer 22

so i think this is really easy understandably bc. there are (5n+1) and (6n+1)
but like a first step of proof we can rewriting the (6n+1) in this way ((5n+1)+1) and from the law of natural numbers the difference betwee two naturale numbers is allways 1
- bc. (6n+1) and (5n+1) has this difference of 1 so - my opinion - for every naturale numbers n from (5n+1) and (6n+1) will result coprimes

@ganeshie8

Answer 23

@jhonyy9 6n + 1 isn't equal to (5n+ 1)+1.
(5n+ 1)+1 = 5n + 2

Answer 24

yes sorry i thought it (5n+n)+1)=(5n+1)+n

Answer 25

And that's why your proof isn't quite right. 5n+ 1 and 6n + 1 doesn't have to be consecutive. If they were consecutive, then you would be right, but take, for example n = 2;
5n + 1 = 11
6n + 1 = 13

Answer 26

or (6n+1)= ((5+1)n +1) =5n+n+1
for n=k

5k+k+1=
so for k=1 this is easy understandably that 5*1+1+1 is consecutive of 5*1+1

7 consec. of 6

so in this way just we use the proof of inductive

for k=k+1 we get

5(k+1) +1 and (5+1)(k+1)+1

5k+6 and 5k+k +6+1

5k+6 and 6k +7

for k=1

11 and

by induction not can being proven ?

Answer 27

or i missed something there ???