Question

Relatively prime numbers

Answer 1

So like just sorta what can we do with them? I know there's a lot out there. I'll start with something I found myself not too long ago. But anyone just feel free to throw stuff out here if you're interested as long as it loosely relates to relatively prime numbers lol.

Answer 2

I was thinking about Euclid's proof of the existence of infinitely many primes. Assume you have all the primes, multiply them all together, then add 1 to it and you get a new number that's relatively prime to ALL of those primes, so it's divisible by some prime not in the list.

So this got me thinking, I could generate a list of all numbers mutually relatively prime to each other that way,

\[a_0\]\[a_1=a_0+1\]\[a_2=a_0a_1+1\]\[a_3=a_0a_1a_2+1\]\[\cdots\]\[a_n=a_0\cdots a_{n-1}+1\]\[a_{n+1}=a_0\cdots a_{n-1}a_n+1\]

Every number generated this way is relatively prime to each other, in other words, for \(n \ne m\), \(\gcd(a_m,a_n)=1\)

I really wanted to find the formula for the nth term in the sequence, but I was only able to figure out this recurrence relation. Here's my derivation of it:

Rearrange this:
\[a_n=a_0\cdots a_{n-1}+1\]
\[a_n-1=a_0\cdots a_{n-1}\]
Plug it in here:
\[a_{n+1}=a_0\cdots a_{n-1}a_n+1\]
\[a_{n+1}=(a_n-1)a_n+1\]

So my recurrence relation is:

\[a_{n+1} = a_n^2 -a_n+1\]

Or you could just look at
\[f(x) = x^2-x+1\]

Repeated iteration of this function always produces numbers relatively prime numbers to any other prior numbers!

Answer 3

Another sequence that generates relatively prime numbers \[a_n = 2^{2^n}+1\]

Answer 4

http://www.wolframalpha.com/input/?i=Table%5B2%5E2%5En%2B1%2C%7Bn%2C1%2C5%7D%5D

Answer 5

Actually that is a cute little proof for infinitude of prime numbers :

Since the sequence has infinitely many terms and none of them share the primes, there must be infinitely many primes too.

Answer 6

Yeah :P

How do I prove that \[\gcd(2^{2^n}+1,2^{2^m}+1)=1\] for all \(m \ne n\)?

Answer 7

Hint:
Use Euclid algorithm.
I would right that down but I'm on phone and I'm going out so... just enjoying the thread..

Answer 8

Let \(m\gt n\) :
\[2^{2^m}+1 \equiv \left(2^{2^n}\right)^{2^{m-n}}+1 \equiv (-1)^{2^{m-n}}+1 \equiv 2 \pmod{2^{2^n}+1}\]

Answer 9

That means, for any two distinct terms in the sequence we have :
\[a_m \equiv 2 \pmod{a_n}\]

Since \(a_m\) and \(a_n\) are odd, we can conlclude that they are relatively prime.

(If they are not relatively prime, the gcd must divide \(2\), which is impossible )

Answer 10

few other proofs of the same are available here
http://math.stackexchange.com/questions/68653/fermat-numbers-and-gcd

Answer 11

That result can be used to show that \(2^{2^n}-1\) has at least \(n\) distinct prime divisors :
\[\omega(2^{2^n}-1)\ge n\]

Answer 12

Interesting, that seems like it would be useful for evaluating multiplicative functions which is kind of a side goal for these. I guess ever since seeing the proof for the relationship between Mersenne primes and perfect numbers and just playing with the totient function I can't seem to stop. Something about relatively prime numbers just gets to me haha.

Answer 13

I think it is due to the multiplicative functions... these are fun in number theory because of the fundamental theorem of arithmetic..

Answer 14

w/o fundamental thm of arithmetic, it seems we cannot do much with multiplicative functions in number theory

Answer 15

Yeah, I am really comfortable with Dirichlet convolutions and the Mobius function and all that cool stuff.

Answer 16

Here is another cool recurrence relation. This generates either 1's or prime numbers :

\[a_n = a_{n-1}+\gcd(a_{n-1},n),~~~a_1=7\]

https://oeis.org/A132199

Answer 17

Woah, cool. I think I'm falling asleep, I'll be back later with some weird or funky identities maybe.

Answer 18

I'm trying to prove above statement... looks very tricky..

Answer 19

http://www.wolframalpha.com/input/?i=solve+a%28n%2B1%29+%3D+%28a%28n%29%29%5E2+-+a%28n%29+%2B+1%2C+a%281%29%3D2

Answer 20

Wonder if there exists a closed form for these recurrence relations..