# Primitive sequences (true or false questions).

• Apr 13th 2009, 03:33 PM
jamix
Primitive sequences (true or false questions).
Let us call a sequence (a_n) primitive if it has the property that gcd(a_i,a_n) = 1, for all 'i' less than n.

Question: State whether the following statements are true or false.

The sequence of mersenne numbers M_n = 2^n -1 is a primitive sequence?

The sequence of mersenne numbers M_p = 2^p -1 (here p shall only take on prime numbers) is a primitive sequence?

The sequence of Fermat numbers 2^(2^n) +1 is a primitive sequence?

(Hard question) The sequence of numbers defined by a_n = 2*3*5....*p_n -1 (p_n is the nth prime number) is a primitive sequence.

^
• Apr 13th 2009, 04:43 PM
NonCommAlg
Quote:

Originally Posted by jamix
Let us call a sequence (a_n) primitive if it has the property that gcd(a_i,a_n) = 1, for all 'i' less than n.

Question: State whether the following statements are true or false.

The sequence of mersenne numbers M_n = 2^n -1 is a primitive sequence?

no. n = 4, i = 2 is a counter-example.

Quote:

The sequence of mersenne numbers M_p = 2^p -1 (here p shall only take on prime numbers) is a primitive sequence?
yes, because for any i < n: $\displaystyle \gcd(2^i - 1, 2^p -1)=2^{\gcd(i,p)} - 1 = 2 - 1 = 1.$

Quote:

The sequence of Fermat numbers 2^(2^n) +1 is a primitive sequence?
yes, becasue for i < n we have: $\displaystyle 2^{2^n} + 1=(2^{2^i})^{2^{n-i}} \equiv 1 \mod 2^{2^i} + 1.$

Quote:

(Hard question) The sequence of numbers defined by a_n = 2*3*5....*p_n -1 (p_n is the nth prime number) is a primitive sequence.
i'd be very surprised if the answer to this one is "yes"! have you checked it for some values of n probably using maple or something?

does anybody here know if a sequence $\displaystyle \{a_n \}$ with this property that for all $\displaystyle m,n: \ \gcd(a_m,a_n)=a_{\gcd(m,n)}$ has any name or not?
• Apr 13th 2009, 06:10 PM
jamix
I didn't use Maple to test p# - 1. If a counterexample doesn't exist for the first few terms, then its probably true (in my opinion). My mathematical arguement is somewhat tricky and unclear though.

Interesting property. I don't know the name for it off the top of my head.

a_n = lcm(a_d1, a_d2,.....a_dk) where each d_i is a proper factor of n.

Example:

Let a_1 = 4, a_2 = 12, a_3 = 20

Then

a_6 = lcm (4,12,20) = 60.

Here are some interesting problems:

1. Show that the property you stated follows.

2. Show that for composite n, a_n = lcm(a_i, a_j) for some i and j such that gcd(i,j) = p (a prime factor of n ).

3. Show that is we know a_p for all primes p, then we find a_n for all n.

4. What kind of sequence would we get by letting a_1 = 1?