MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: A (little?) problem in Number Theory

O.K. Here is a solution. It has little to do with Mathematica. Since, 
however, your question managed to pass the moderator I hope my proof will
also do so:-) However, to make it more likely I shall give a Mathematica
implementation of this solution at the end, although in reality it is
completely useless: you get an overflow before you get the fifth term of the

If I understand you correctly, you want to show that you can choose a
subsequence of the sequence {(2^n)-3} consisting of numbers which are
mutually relatively prime. I shall first prove the following lemma:

Lemma. Given an odd integer m, there is a number of the form 2^k -3 which is
relatively prime to m.

Proof.  Consider 2^EulerPhi[m]. By Euler's theorem (generalization of
Fermat's little theorem) this is equal to 1 mod m. Hence 2^EulerPhi[m]-3
leaves the remainder -2 on division by m. Since m is odd it has to be
relatively prime to m.

Now we proceed as follows. Start with n=1, so you get 1 and n=2, so you get
5. Take their product, which is 5. Now we take 2^EulerPhi[5]-3=16-3=13.
which is relatively prime to both 1 and 5. So the new sequence is {1,5,13}.
Multiply all these numbers to get 65 and take 2^EulerPhi[65]-3 as your next
term. This is as far as you can go with Mathematica. Here is an

bobic0 = {2^2 - 3, 2^3 - 3};
next[l_List] := Append[l, 2^EulerPhi[Apply[Times, l]] - 3]
bobic[n_] := Nest[next, bobic0, n]

{1, 5, 13}

{1, 5, 13, 281474976710653}


General::"ovfl": "Overflow occurred in computation."
{1, 5, 13, 281474976710653, Overflow[]}
Andrzej Kozlowski
Toyama International University

>From: Freed Bobic <freed at>
To: mathgroup at
>To: mathgroup at
>Subject: [mg19954] [mg19914] A (little?) problem in Number Theory
>Date: Tue, 21 Sep 1999 02:22:48 -0400

> Hello everybody,
> I need a little help. My problem sounds easy, but I don't think it is:
> Show that there is an infinite subsequence of {(2^n)-3} with pairwise
> coprime elements.
> I tried it in different ways, but I didn't manage it.
> For example, thinking about prime numbers as elements of that sequence
> and prooving somthing like:
> "there are infinitly many prime numbers of the form 2^n-3"
> gave no result. It seems not to be that easy: think about that there is
> no proove about the number of the Mersenne Prime Numbers (2^n-1)...
> Well, I don't know. Please try it and mail your results directly to
> freed at - because I'm not able to visit the groups very often.
> Thanks a lot,
> Gregor Gruening (freed at
> Und nochmal fuer deutschsprechende Mathematiker:
> Ich habe ein Problem mit der Folge {(2^n)-3}. Ich soll zeigen, dass
> es eine unendliche Teilfolge mit paarweise teilerfremden Elementen gibt.
> Klingt leicht, ist es aber nicht - denke ich zumindest. Ich habe
> jedenfalls schon sehr mit dem Problem gekaempft. Der naheliegenste
> Weg, zu beweisen, es gebe unendlich viele Primzahlen der Form 2^n-3,
> fuehrt jedenfalls zu keinem schnellen Ergebniss. Man kommt naemlich
> recht schnell zu dem Problem, zeigen zu muessen, es gebe unendlich
> viele Mersennesche Primzahlen (2^n-1) - und das ist meines Wissens
> noch niemandem gelungen.
> Es muss irgendwie recht elementar gehen. Ich brauche einen guten Tip.
> Fuer weitere Infos stehe ich natuerlich gerne zu Verfuegung.
> Schreibt mir schnell (am besten auch direkt an meine Adresse).
> Gregor Gruening (freed at

  • Prev by Date: Re: Re: How to find solutions for conditioned equations?
  • Next by Date: Re: Plot, Table.
  • Previous by thread: A (little?) problem in Number Theory
  • Next by thread: Symbolic Derivatives with respect to a vector