120. Esponenziali meno 1 e fattoriali

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

120. Esponenziali meno 1 e fattoriali

Messaggio da <enigma> »

Risolvere negli interi positivi $(2^a-1)(3^b-1)=c!$.
[Mathematical Reflections]
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da jordan »

Apparso anche qui viewtopic.php?f=15&t=14232 , e alla fine dimenticato..

Ricordo che io spedii la soluzione a questo problema, vedo se la ritrovo ;)

Edit: oddio, e' l'unica issue in cui non hanno pubblicato il file delle soluzioni, speravo di ritrovarla -.-
Comunque si vede già "a occhio" la strada da prendere per risolverlo
The only goal of science is the honor of the human spirit.
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da <enigma> »

Allora se qualcuno dovesse avere bisogno di un hint, posso dire che la mia soluzione passa per
Testo nascosto:
il teorema di Zsigmondy.
Ma ne esistono altre anche più semplici.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da Drago96 »

Osservazione da nabbo: $3^b-1\leq c!$ (con l'uguaglanza che vale solo con $b=1$), dunque per numeri "abbastanza grossi" questo significa $v_2(3^b-1)\leq v_2(c!)$ e dato che non ci sono fattori 2 in $2^a-1$, le soluzioni non sono infinite, e direi anche abbastanza piccole...

Il vero problema è capire quando i numeri sono "abbastanza grandi" per far sì che $v_2(3^b-1)< v_2(c!)$ :lol:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da <enigma> »

Quel che scrive Maioc92 nell'altro topic :wink: Attenzione che è $v_2(3^b-1)=v_2(c!)$ a prescindere dalle dimensioni dei numeri (e $x \leq y$ non implica $v_2(x) \leq v_2(y)$...)
Lifting the Exponent ti dice niente?
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da Hawk »

Risolvo l'equazione $ 3^m-1=2^n $.
1) Se $ m $ è pari sostituisco $ m=2t $. Riscrivo come $ (3^t+1)(3^t-1)=2^n $.

Quindi si deve avere che $ \begin{cases} 3^t+1=2^k \\ 3^t-1=2^s \\ 2^k \cdot 2^s=2^n \end{cases} $. Sottraggo la seconda equazione dalla prima ed ottengo che: $ 2^k-2^s=2 $, adesso la sequenza delle potenze di $ 2 $ è: $ 1,2,4,8,16... $, e poiché la funzione esponenziale $ y=2^n $ è strettamente crescente si ha che la differenza di due potenze consecutive diventa sempre maggiore. Quindi osservando le potenze del 2 si trova che l'unica soluzione è per $ k=2 $ e $ s=1 $. Trovo adesso i valori di $ 3^t $, soluzioni del sistema, sostituendo $ 3^t=3 $ che è verificata per $ t=1 $. Questa è l'unica soluzione.

2) Provo i casi di $ n<3 $ e trovo la soluzione $ m=1 $ ed $ n=1 $. Assumo quindi $ n>3 $. Adesso considero il caso in cui $ m=2l+1 $. Quindi $ 3^{2l+1}-1=2^n $, allora modulo $ 4 $ si ottiene che $ 3^{2l+1}-1 \equiv 0 \pmod{4} $, ma ciò è assurdo perché $ 3^{2l+1}\equiv 3 \pmod{4} $.

Quindi l'unica soluzione è data per $ m=2 $ e $ n=3 $.

Passo ora a risolvere l'equazione del problema: $ (2^a-1)(3^b-1)=c! $
Per quanto avete detto $ v_2(3^b-1)=v_2(c!) $, ma $ 3^b-1 $ può contenere soltanto $ 1 $ o $ 3 $ fattori 2. Da cui si ricava che $ c<6 $.
Quindi 1) $ c=1 $ e non ottengo soluzioni;
2) $ c=2 $ ed ottengo la soluzione $ a=1 $ e $ b=1 $;
3)$ c=3 $ ed ottengo la soluzione $ a=2 $ e $ b=1 $;
4) $ c=4 $ ed ottengo la soluzione $ a=2 $e $ b=2 $;
5) $ c=5 $ ho che $ 8(2^a-1)=1\cdot 2 \cdot 3 \cdot 4 \cdot 5 $ da cui $ a=4 $ e $ b=2 $.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da ma_go »

$80\cdot 63 = 5040$.
e comunque è vero che tutti i fattori 2 di $c!$ sono in $3^a-1$, ma non è detto che non ce ne siano anche altri.
<enigma> ha scritto:Lifting the Exponent ti dice niente?
qui se ne può fare anche a meno*.. chi si butta?

*o quantomeno dimostrarlo a manina in un caso particolare, che non è difficile..
Omar93
Messaggi: 79
Iscritto il: 15 mar 2011, 18:58

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da Omar93 »

Hawk ha scritto:Risolvo l'equazione $ 3^m-1=2^n $
Non capisco questo punto. Come fai a dirlo?? Non dovrebbe invece essere $ 3^m-1=h 2^n $ h appartiene ad N
$ 2^{43 112 609} - 1 $
Chuck Schuldiner
Messaggi: 308
Iscritto il: 11 feb 2012, 14:37
Località: Hangar 18

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da Chuck Schuldiner »

Intanto vedo che ci sono le coppie (c, a, b) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (5, 4, 2), (6, 2, 4), mentre per c=7, 8, 9 e 10 non si trovano a e b. Adesso per LTE $ v_2(3^b-1)=v_2(b)+2 $ e $ v_3(2^a-1)=v_3(a)+1 $. Inoltre, escludendo le soluzioni piccole già provate, $ v_2(c!)\geq \frac {c}{2} $ e $ v_3(c!)\geq \frac {c}{3} $. Quindi $ LHS\geq (2^{3^{\frac{c}{3}-1}}-1)(3^{2^{\frac{c}{2}-2}}-1) $.
Siccome in c! c'è l'11 e ordine mod11 di 3 e 2 è multiplo di 5, uno dei 2 esponenti andrebbe moltiplicato per 5. Questo per dire che si può tranquillamente supporre
$ LHS\geq 2^{3^{\frac{c}{3}}}3^{2^{\frac{c}{2}}} $. Inoltre $ c!<c^c $. Ora dimostro per induzione che per c sufficientemente grande
$ 2^{3^{\frac{c}{3}}}3^{2^{\frac{c}{2}}}\geq c^c $:
passo base: per c=11 $ 11^{11} $ è più piccolo di $ 10^{12} $ circa, mentre l'altro termine è più grande di $ 2^{27}3^{32} $, che supera di gran lunga i $ 10^{12} $.
passo induttivo: $ 2^{3^{\frac{c+1}{3}}}3^{2^{\frac{c+1}{2}}}=2^{3^{\frac{c}{3}}3^{\frac{1}{3}}}3^{2^{\frac{c}{2}}2^{\frac{1}{2}}}=(2^{3^{\frac{c}{3}}})^{3^{\frac{1}{3}}}(3^{2^{\frac{c}{2}}})^{2^{\frac{1}{2}}}=(2^{3^{\frac{c}{3}}}3^{2^{\frac{c}{2}}})^{2^{\frac{1}{2}}}\geq c^{c\sqrt{2}}=c^{c+1}c^{(\sqrt{2}-1)c-1}\geq c^{c+1}2^{c+1}\geq (2c)^{c+1}\geq (c+1)^{c+1} $.
https://www.youtube.com/watch?v=35bqkTIcljs

Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto

ho fatto più allo scritto in normale che alla maturità \m/

non aprire questo link

un pentacolo fatto col mio sangue
Testo nascosto:
Immagine
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da Hawk »

Per c=7 c'è la soluzione di ma_go b=4 e a=6.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 120. Esponenziali meno 1 e fattoriali

Messaggio da jordan »

Mi ricordavo di aver risolto questo problema anni fa, e infatti ho ritrovato la soluzione

L'ho postata qui, ma il latex non era molto simpatico a wordpress questa volta (vedro' di modificarlo appena posso, di modo che sia leggibile)

In ogni caso, ho postato sotto la versione pdf..



Edit (backup tex): First, observe that if $latex c\le 7$ then we can easily see that unique solutions are $latex (a,b,c)=\{(1,1,2),(2,1,3),(2,2,4),(4,2,5),(6,4,7)\}$. So, assuming that $latex c\ge 8$ then $latex 2^7\cdot 3^2\mid 8!\mid c!=(2^a-1)(3^b-1)$.

We must have $latex \upsilon_2(c!)=\upsilon_2\left((2^a-1)(3^b-1)\right)=\upsilon_2(3^b-1)$: we’ll show by PMI that there exists $latex B \in 2\mathbb{N}+1$ such that $latex b=2^{\upsilon_2(c!)-2}\cdot B$. In fact, $latex \upsilon_2(3^{2^1}-1)=3$ and supposed that $latex \upsilon_2(3^{2^r}-1)=r+2$ for some $latex r\in \mathbb{N}_0$ then there exists $latex h \in 2\mathbb{N}+1$ such that $latex 3^{2^r}=h\cdot 2^{r+2}+1$. It implies that $latex 3^{2^{r+1}}=h^2\cdot 2^{2r+4}+h\cdot 2^{r+3}+1$ that is $latex \upsilon_2(3^{2^{r+1}}-1)=r+3$, and the induction is complete. Moreover, let $latex u\in 2\mathbb{N}+1$ fixed, so $latex 3^{2^r\cdot u}=\left(h\cdot 2^{r+2}+1\right)^u=k\cdot 2^{r+3}+uh\cdot 2^{r+2}+1$ for some $latex k \in \mathbb{N}_0$, and it is enough for our aim.

At the same way, since $latex \upsilon_3(c!)=\upsilon_3\left((2^a-1)(3^b-1)\right)=\upsilon_3(2^a-1)$ we can show that there exists $latex A \in \mathbb{N}\setminus 3\mathbb{N}$ such that $latex a=2\cdot 3^{\upsilon_3(c!)-1}\cdot A$. In fact $latex 2$ the unique (since $latex \varphi(\varphi(3))=1$) generator of $latex \mathbb{Z}/3\mathbb{Z}$, so it is also a generator of $latex \mathbb{Z}/3^x\mathbb{Z}$ for all $latex x \in \mathbb{N}_0$: consider $latex p \in \mathbb{P}\setminus\{2\}$ fixed and let $latex g$ one of the $latex \varphi(\varphi(p))$ generators of $\mathbb{Z}/p\mathbb{Z}$. Suppose that for some $latex l \in \mathbb{N}_0$ we have that $latex g$ is also a generator of $latex \mathbb{Z}/p^l\mathbb{Z}$; it means that $latex \displaystyle \prod_{i \in \mathbb{N} \cap [1,\varphi(p^l)-1]}{\left\{\frac{g^i-1}{p^l}\right\}}>0$. Let’s verify our aim by PMI: if by contradiction there exist $latex i \in \mathbb{N} \cap [1,\varphi(p^{l+1})-1]$ such that $latex \upsilon_p(g^i-1) \ge l+1$ then we must have $latex \varphi(p^l) \mid i$ by assumption of the induction step. Then there should exist $latex j\in \mathbb{N}\cap [1,p-1]$ such that $latex \upsilon_p(g^{\varphi(p^l)j}-1)\ge l+1$. But if we suppose that $latex \upsilon_p(g^{p-1}-1)=1$ then we can easily see that $latex \right(g^{\varphi(p^l)}\right)^j=e\cdot p^{l+1}+wj\cdot p^l+1$ for some $latex (e,w) \in \mathbb{N}_0^2$ such that $latex \text{gcd}(p,w)=1$. The induction is complete, and it works in our case since $latex \upsilon_3(2^{3-1}-1)=1$, so all assumptions are satisfied.

Now since $latex \upsilon_2(3^b-1)\ge 7$ we deduce that $latex b\ge 2^{7-2}=32$, hence $latex c!=(2^a-1)(3^b-1)\ge (3^{32}-1)\ge 8\cdot 3^{30}\ge 8\cdot(2\cdot 10)^{10}$ $=2^{13}\cdot 10^{10} > 2^3\cdot 10^{13}$. On the other hand $latex 6!<10^3$, $7\cdot 8\cdot 9\cdot 10<10^4$, $latex 11\cdot 12<\frac{3}{2}\cdot 10^2$, $latex 13\cdot 14<2\cdot 10^2$ and $latex 15\cdot 16<\frac{8}{3}\cdot 10^2$: multiplying all inequalities we get $latex 16!<2^{3}\cdot 10^{13}$. It means that if a solution with $latex c\ge 8$ exists then $latex c\ge 17$ and, consequently, $latex \upsilon_2(c!)=\upsilon_2(3^b-1)\ge 15$ and $latex \upsilon_3(c!)=\upsilon_3(2^a-1)\ge 6$. But again from previous observations it means that $latex a\ge 2\cdot 3^5>400$ and $latex b\ge 2^{13}>8001$. As before it implies that that $latex c!>2^{400}\cdot 3^{8001}>10^{120}\cdot(2\cdot 10)^{\frac{8001}{3}}=10^{2787}\cdot 2^{2667}>10^{2787+3\cdot 266}>10^{3000}$. And on the other hand clearly $latex 1000!<(1000)^{1000}=10^{3000}$: it means that if a solution with $latex c\ge 8$ exists then $latex c>1000$. (It is obvious that continuing with this algorithm we get that $latex c$ need to be arbitrarily large, but I wanted to search a alternative clearer way).

It is well-known that for all $latex (p,n) \in \mathbb{P}\times \mathbb{N}_0$ the identity $latex \upsilon_p(n!)(p-1)=n-s_p(n)$ holds, where $latex s_p(\cdot)$ denotes the sum of digits of $latex n$ written in base $latex p$. In particular $latex \upsilon_2(n!)=n-s_2(n)\ge n-\lfloor \text{log}_2(n)\rfloor \ge n-\text{log}_2(n)$ and $latex \upsilon_3(n!)=\frac{1}{2}\left(n-s_3(n)\right)\ge \frac{n}{2}-\lfloor \text{log}_3(n)\rfloor \ge \frac{n}{2}-\ln(n)$.

Again we can note that for all positive integer $latex x$ the inequality $latex 2^x\cdot x!<(x+1)^x$ holds (that is also a direct consequence of Stirling approssimation). In fact if $latex x \in 2\mathbb{N}+1$ then $latex \displaystyle x!=\left(\frac{x+1}{2}\right)\cdot \prod_{i \in \mathbb{N} \cap [1,\frac{x-1}{2}]}{\left(\left(\frac{x+1}{2}\right)^2-i^2\right)}<\left(\frac{x+1}{2}\right)^x$. And if $latex x \in 2\mathbb{N}$ then $latex \displaystyle x!=\prod_{i\in 2\mathbb{N}+1 \cap [1,\frac{x}{2}]}{\left(\left(\frac{x+1}{2}\right)^2-\left(\frac{2i-1}{2}\right)^2\right)}<\left(\frac{x+1}{2}\right)^x$.

And if $latex (2^a-1)(3^b-1)=c!$ for some positive integers $latex a,b,c$ such that $latex c \ge 8$ then also the inequality $latex \displaystyle \left(2^{2\cdot 3^{\upsilon_3(c!)-1}\cdot A}-1\right)\left(3^{2^{\upsilon_2(c!)-2}\cdot B}-1\right)<\left(\frac{c+1}{2}\right)^c$ holds.

In particular, since $\upsilon_2(c!)\ge 4$ and $\upsilon_3(c!)\ge 2$ then $a\ge 6$ and $b\ge 4$, hence $(2^a-1)(3^b-1)\ge \left((1-2^{-6})2^a\right)\cdot \left((1-3^{-4})3^b\right)=2^{a-2}\cdot 3^{b-2}\cdot 5\cdot 7$.

And because of $latex \min\{A,B\}\ge 1$ then the inequality $latex \displaystyle 2^{2\cdot 3^{\upsilon_3(c!)-1}-2+c}\cdot 3^{2^{\upsilon_2(c!)-2}-2}\cdot 5\cdot 7<(c+1)^c$ holds. Now, observing that $latex 5\cdot 7>2^5$ and $latex 3^2>2^3$ and taking in mind previous inequalities about $latex \upsilon_p(c!)$, we have that the weaker inequality $latex \displaystyle 2^{2\cdot 3^{\frac{c}{2}-\ln(c)-1}+3\cdot 2^{c-\text{log}_2(c)-3}+c}<(c+1)^c$ holds, that is equivalent to $latex \displaystyle 2\cdot 3^{\frac{c}{2}-\ln(c)-1}+3\cdot 2^{c-\text{log}_2(c)-3}<c\cdot \left(\text{log}_2(c+1)-1\right)$.

Proceeding in this way, we have that $latex c\cdot \left(\text{log}_2(c+1)-1\right)\le c^2=3^{2\text{log}_3(c)}<3^{2\text{log}_2(c)}$ and from AM-GM (and because $latex \ln(c)<\text{log}_2(c)$ and $2^8>3^5$):
$latex \displaystyle 2\cdot 3^{\frac{c}{2}-\ln(c)-1}+3\cdot 2^{c-\text{log}_2(c)-3}>$ $latex \displaystyle 2\cdot 3^{\frac{1}{2}\left((\frac{5}{8}+\frac{c}{2}-\text{log}_2(c)-1)+(1+\frac{5}{8}\left(c-\text{log}_2(c)-3\right))\right)}>$ $latex \displaystyle 3^{\frac{9}{16}c-\frac{13}{16}\text{log}_2(c)}$.

It implies that $latex \displaystyle \frac{9}{16}c-\frac{13}{16}\text{log}_2(c)<2\text{log}_2(c)$, that is equivalent to $latex 2^c<c^5$. Since $c>10^3$, suppose that $latex c\in \mathbb{Z}\cap [10^{s-1},10^s)$ for some integer $latex s \ge 4$, and because $latex 10^3<2^{10}$, we have finally that $latex 10^{10^{s-2}}<10^{\frac{3}{10}c}<2^c<c^5<10^{5s}$, that is clearly a contradiction.
The only goal of science is the honor of the human spirit.
Rispondi