Re: A (little?) problem in Number Theory
- To: mathgroup at smc.vnet.net
- Subject: [mg19954] Re: [mg19914] A (little?) problem in Number Theory
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Wed, 22 Sep 1999 04:11:27 -0400
- Sender: owner-wri-mathgroup at wolfram.com
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
sequence.
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
implementation:
In[1]:=
bobic0 = {2^2 - 3, 2^3 - 3};
In[2]:=
next[l_List] := Append[l, 2^EulerPhi[Apply[Times, l]] - 3]
In[3]:=
bobic[n_] := Nest[next, bobic0, n]
In[4]:=
bobic[1]
Out[4]=
{1, 5, 13}
In[5]:=
bobic[2]
Out[5]=
{1, 5, 13, 281474976710653}
however
In[6]:=
bobic[3]
General::"ovfl": "Overflow occurred in computation."
Out[6]=
{1, 5, 13, 281474976710653, Overflow[]}
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp
----------
>From: Freed Bobic <freed at muenster.de>
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>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 muenster.de - because I'm not able to visit the groups very often.
>
> Thanks a lot,
> Gregor Gruening (freed at muenster.de)
>
> 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 muenster.de)
>