Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Problema 119.

Messaggio da jordan » 03 ago 2012, 17:17

Problema 119 da qui:
jordan ha scritto:Trovare tutti gli interi positivi $n$ tali che l'insieme $\{n,n+1,n+2,\ldots,n+9\}$ può essere partizionato in due sottoinsiemi a prodotto costante.
<enigma> ha scritto:Se $11$ divide uno fra quei dieci numeri abbiamo un assurdo perché non può dividerne un altro ma il prodotto degli elementi di ciascuno dei due sottoinsiemi ha il fattore $11$. Siano $S_1$ e $S_2$ i due insiemi e $P$ il prodotto degli elementi di ciascuno: allora $\prod _{k=0}^9 (n+k) \equiv -1 \pmod {11}$, ma anche $=\prod_{i \in S_1} i \prod_{j \in S_2} j \equiv P^2$; tuttavia $P^2 \equiv -1 \pmod {11}$ è assurdo. Tale partizione è quindi impossibile.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Problema 120.

Messaggio da jordan » 03 ago 2012, 17:19

Problema 120 da qui:
<enigma> ha scritto:Risolvere negli interi positivi $(2^a-1)(3^b-1)=c!$.
[Mathematical Reflections]
Soluzione postata qui (in basso c'è direttamente il pdf)
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

121

Messaggio da jordan » 22 ott 2012, 13:47

Problema 121 da qui
jordan ha scritto:121. (Own) notazioni: Siano $\text{gpf}(x)$ e $\text{lpf}(x)$ il piu' grande fattore primo e il piu' piccolo fattore primo che dividono un intero $x>1$ e $\upsilon_p(x)$ la valutazione p-adica di $x$.
Definiamo infine la funzione aritmetica $f(\cdot):\mathbb{N}_0\to \mathbb{N}_0$ di modo tale che :
$f(n)=1$ se $n=1$ oppure se $\text{gpf}(n)<100$
$f(n)=\text{lpf}\left(n\prod_{p\in \mathbb{P}\cap[1,100]}{p^{-\upsilon_p(n)}}\right)$ altrimenti.

In altre parole, f(n) e' il piu' piccolo primo che divide n, che è maggiore di 100; se tale primo non esiste allora f(n)=1.


Dimostrare che, fissata una costante $C>10^{40}$, esistono infiniti interi positivi $n$ tali che $C<f(n)<f(n+1)<f(n+2)<...<f(n+99)<C^2$.
Leonida ha scritto:Lemma: esistono almeno 100 numeri primi $p$ tali che $C < p < C^2$.
Dim.: dimostro per induzione su $k$ che tra $C$ e $2^k C$ vi sono almeno $k$ numeri primi.
Passo base: $k=1$. Segue dal il Teorema di Chebyshef (o Postulato di Bertrand), il quale afferma che esiste almeno un primo tra $C$ e $2C$, purchè $C > 1$.
Passo induttivo: supponiamo esistano $k$ numeri primi tra tra $C$ e $2^k C$. Ancora per il Teorema di Chebyshef, esiste almeno un primo tra $2^k C$ e $2^{k+1} C$, perciò tra $C$ e $2^{k+1} C$ vi sono almeno $k+1$ primi e il passo induttivo è verificato.
In particolare esistono almeno 100 numeri primi $p$ tali che $C < p < 2^{100} C$. Ma $2^{100} C < 8^{34} C < 10^{34} C < 10^{40} C < C^2$ è vera poichè per ipotesi $C > 10^{40}$, da cui segue il Lemma.
Indico con $101 < 103 < ... < p_{C-1} \leq C$ i primi compresi tra 100 e $C$ e con $C < p_{C}< p_{C+1}< ... < p_{C+99} < C^2$ cento numeri primi compresi tra $C$ e $C^2$ (esistono per il Lemma). E' sufficiente scegliere $n$ in modo che risolva il seguente sistema di congruenze:
\[
\left\{
\begin{array}{l}
n \equiv 1 \pmod {101} \\
n \equiv 1 \pmod {103} \\
n \equiv 1 \pmod {...} \\
n \equiv 1 \pmod {p_{C-1}} \\
n +i \equiv 0 \pmod {p_{C +i}}, \forall i, 0 \leq i \leq 99
\end{array}
\right.
\]
Innanzitutto per il Teorema Cinese del Resto esistono infinite soluzioni a questo sistema di congruenze, dato che i moduli sono a due a due coprimi. Inoltre, se $101 \leq p \leq p_{C-1}$, $n +i \equiv i+1 = 1, ... , 100 \not \equiv 0 \pmod p$.
Pertanto $f(n +i) \geq p_{C} > C$, $\forall i, 0 \leq i \leq 99$.
Allora $f(n +i) = p_{C +i}$ ; di conseguenza $f(n) < f(n+1) < ... < f(n +99) < C^2$ è vera perchè lo è $p_C < p_{C +1} < ... < p_{C +99} < C^2$. In conclusione, si ha $C < f(n) < f(n+1) < ... < f(n +99) < C^2$ che è la tesi.
P.S.: dato che questa soluzione è un po' barata, se qualcuno ne ha una che non passi per il Postulato di Bertrand mi sembra giusto cedergli il testimone della staffetta.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

122.

Messaggio da jordan » 22 ott 2012, 13:48

Problema 122 da qui:
jordan ha scritto:Dal 4 agosto Leonida non è si è fatto piu' vivo sul forum, e nessuno ha voluto postare quello nuovo, per cui..

Siano a e b due interi positivi fissati. Mostrare che esiste solo un numero finito di interi positivi n tali che $\displaystyle \left(a+\frac{1}{2}\right)^n+\left(b+\frac{1}{2}\right)^n$ è intero.
Ido Bovski ha scritto:$\displaystyle \left(a+\frac{1}{2}\right)^n+\left(b+\frac{1}{2}\right)^n=\frac{(2a+1)^n+(2b+1)^n}{2^n}=\frac{1}{2^n}\sum_{k=0}^n 2^k\binom{n}{k}(a^k+b^k)$
  • Se $n\neq 0$ è pari, allora $2^n\nmid (2a+1)^n+(2b+1)^n$, infatti
    $\displaystyle \sum_{k=0}^n 2^k\binom{n}{k}(a^k+b^k)\equiv \sum_{k=0}^1 2^k\binom{n}{k}(a^k+b^k)\equiv 2+2n(a+b)\equiv 2 \not\equiv 0 \pmod 4$
    Dunque non esiste un $n$ che soddisfa le condizioni richieste.
  • Se $n$ è dispari, allora, poiché $2|(2a+1)+(2b+1)$, per LTE
    $\nu_2((2a+1)^n+(2b+1)^n)=\nu_2((2a+1)+(2b+1))=1+\nu_2(a+b+1)$
    Pertanto $2^n|(2a+1)^n+(2b+1)^n$ per $ \lceil (1+\nu_2(a+b+1))/2 \rceil $ scelte di $n$.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

123

Messaggio da jordan » 22 ott 2012, 13:49

Problema 123 da qui:
Ido Bovski ha scritto:Sia $p$ un numero primo. Dato un $a\in\mathbb{Z}$ tale che $\gcd(a, p!)=1$, dimostrare che $p!|a^{(p-1)!}-1$.
Se a $p$ primo si sostituisce un $n\in\mathbb{N}$ libero da quadrati, l'enunciato è ancora vero?
jordan ha scritto:Dai due interi $a,b$ possiamo affermare che $a \mid b$ se e solo se $\upsilon_q(a)\le \upsilon_q(b)$ per ogni $q \in \mathbb{P}$.
Adesso e' necessario (e sufficiente) mostrare tale disuguaglianza per tutti i primi $q\le p$: fissato un tale $q$ infatti abbiamo in particolare che $q\mid p! \implies \text{gcd}(a,q)=1$ per cui $\displaystyle \upsilon_q(a^{(p-1)!}-1)=$ $\displaystyle \upsilon_q((a^{q-1})^{(p-1)!/(q-1)}-1)=$ $ \displaystyle \upsilon_q(a^{q-1}-1)+\upsilon_q(\frac{(p-1)!}{q-1})$ $=\displaystyle \upsilon_q(a^{q-1}-1)+\upsilon_q((p-1)!)$ (per LTE e T.di Fermat). Affinche' $\upsilon_q(p!) \le \upsilon_q(a^{(p-1)!}-1)$ dobbiamo quindi mostrare in modo equivalente che $\upsilon_q(p!) \le \upsilon_q(a^{q-1}-1)+\upsilon_q((p-1)!)$ che e' vera se e solo se $\upsilon_q(p) \le \upsilon_q(a^{q-1}-1)$ per ogni primo $q \le p$ e intero $a$ coprimo con $p!$.

E' ovvio adesso che, se $\mu(p)\neq 0$ allora la divisibilità e' sempre verificata, difatti $\displaystyle \upsilon_q(p) \in \{0,1\}$ e $\upsilon_q(a^{q-1}-1) \ge 1$. []
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Staffetta tdn

Messaggio da jordan » 22 ott 2012, 13:50

Problema 124 da qui:
jordan ha scritto:Sia dato un intero $ a \ge 3 $. Mostrare che esiste un intero $ n $ con esattamente 2012 divisori primi tale che $ n\mid (a^n+1) $
nobu ha scritto:Voglio dimostrare che dati 2 interi $a\geq 3$ e $k\geq 1$, esiste un intero $n$ con esattamente $k$ divisori primi t.c. $n\mid a^n+1$.

Distinguo 2 casi:
  • Se $a+1$ non è una potenza di 2, dimostro per induzione su $k$:
    PASSO BASE: $k=1$. Scelgo $n=q$ con $q$ primo dispari che divide $a+1$, allora $q\mid a+1\mid a^q+1$.
    PASSO INDUTTIVO: $k\to k+1$. Per ipotesi induttiva ho $n$ intero con esattamente $k$ divisori primi t.c. $n\mid a^n+1$.
    Considero un primo dispari $q$ che divide $n$ (che esiste perchè all'inizio ho preso un primo dispari che divide $a+1$), allora ho che $nq^\alpha \mid a^{nq^\alpha}+1$ per ogni $\alpha$ intero positivo, dato che $n\mid a^n+1\mid a^{nq^\alpha}+1$ e per LTE vale $\upsilon_q(a^{nq^\alpha}+1)=\upsilon_q(a^n+1)+\alpha$.
    Voglio dimostrare quindi che esiste un primo $p$ tale che $p\mid a^{pnq^\alpha}+1$, ma $p\nmid nq^\alpha$; avrei quindi che $pnq^\alpha$ ha esattamente $k+1$ divisori primi e $pnq^\alpha\mid a^{pnq^\alpha}+1$.
    Ma $p\mid a^{pnq^\alpha}+1 \iff p\mid a^{nq^\alpha}+1$, quindi quello che voglio equivale a dimostrare che esiste $\alpha$ t.c. $a^{nq^\alpha}+1$ ha dei divisori primi che non dividono $n$, ma ciò è facilmente verificabile perchè aumentando $\alpha$ la valutazione $p$-adica dei primi che dividono $n$ rimane la stessa tranne che per $q$, ma quindi $a^{nq^\alpha}+1$ diventa "troppo grande" per avere solo primi che dividono anche $n$.
  • Se $a+1$ è una potenza di 2 c'è qualcosa da sistemare nel passo base, perchè non posso scegliere un primo $q$ dispari t.c. $q\mid a+1$.
    Quindi se $k=1$ scelgo $q=2$ che divide $a+1$ e ho quindi che $2\mid a^2+1$.
    Se $k=2$ voglio quindi dimostrare che esiste un primo dispari che divide $a^2+1$, ma questo è vero perchè $a^2+1\equiv 2 \pmod 4$.
    Tutto il resto è uguale a prima.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

125

Messaggio da jordan » 22 ott 2012, 13:53

Problema 125 da qui:
nobu ha scritto:Sia $a_0,a_1,a_2,...$ una successione di numeri interi positivi tali che $(a_{i+2},a_{i+1})>a_i$ per ogni $i\geq0$.
Dimostrare che $a_n\geq 2^n$ per ogni $n\geq 0$.
jordan ha scritto:Sono bboypa su Mathlinks, e ricordavo di aver risolto questo problema tempo addietro, difatti:
bboypa ha scritto:
April ha scritto:Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i + 1}) > a_{i - 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$.
Our aim $ a_n \ge 2^n$(*) is true for $ n \in \{0,1\}$, in fact $ a_1=1$ would imply $ 1= (a_2,a_1)>a_0 \in \mathbb{N}_0$, absurd. It is also true that $ \{a_n\}_{n \in \mathbb{N}}$ is strictly incrasing since $ \min\{a_{n+1},a_{n+2}\}$ $ \ge (a_{n+1},a_{n+2})$ $ >a_n$. Now if (*) is true for $ n \in \{0,1,\ldots,n-1\}$ then it is true also for $ n$: in fact we have $ a_n-a_{n-1}$ $ \ge (a_n-a_{n-1},a_{n-1})$ $ =(a_n,a_{n-1}) >a_{n-2} \implies$ $ a_n > a_{n-1}+a_{n-2}$. Now if $ \frac{a_{n-1}}{3} \ge (a_{n-1},a_n)> a_{n-2}$ then we are done since $ a_n>a_{n-1}+a_{n-2} \ge 4a_{n-2} \ge 2^n$. Otherwise $ \frac{a_{n-1}}{2}=(a_n,a_{n-1})$. Now if $ a_n \ge 2a_{n-1}$ we are done, otherwise it means that $ 2 \mid a_{n-1}$, $ 3 \nmid a_{n-1}$ and $ a_n=\frac{3}{2}a_{n-1}$. Now if $ \frac{a_{n-1}}{4} \ge a_{n-2} \implies a_n>a_{n-1} \ge 2^n$, in the last last case (since $ 3 \nmid a_{n-1}$) we must have $ (a_{n-2},a_{n-1})=\frac{a_{n-1}}{2}$, but $ \frac{a_{n-1}}{2}=(a_n,a_{n-1})>a_{n-2}=\frac{a_{n-1}}{2}$, contradiction.
Original thread: qui (c'è anche una soluzione che usa un'altra strada se non ricordo male)
Proposed by Morteza Saghafian, Iran, IMO Shortlist 2008
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

126

Messaggio da jordan » 22 ott 2012, 13:53

Problema 126 da qui:
jordan ha scritto:Dimostrare che per ogni coppia di interi positivi $m,n$ vale: $m!n!(m+n)!$ divide $(2n)!(2m)!$

Ps. IMO 1972 O.o
bĕlcōlŏn ha scritto:$ \textbf{Lemma} $:
$ \lfloor a \rfloor + \lfloor b \rfloor + \lfloor a+b \rfloor \leq \lfloor 2a \rfloor + \lfloor 2b \rfloor $

Per la dimostrazione considero $ a = \lfloor a \rfloor + \epsilon_1 $ con $ \epsilon_1 < 1 $, e $ b=\lfloor b \rfloor + \epsilon_2 $ con $ \epsilon_2 < 1 $. Ci sono due casi:
-Caso 1: $ \epsilon_1+\epsilon_2 < 1 $. In tal caso $ LHS = 2(\lfloor a \rfloor + \lfloor b \rfloor) \leq \lfloor 2a \rfloor + \lfloor 2b \rfloor $, poiché $2\lfloor a \rfloor \leq \lfloor 2a \rfloor$ abbastanza chiaramente.
-Caso 2: $ 1\leq \epsilon_1+\epsilon_2 < 2 $. In tal caso sicuramente almeno uno fra $ \epsilon_1,\epsilon_2 $ deve essere $ \geq 0.5 $. Il che vuol dire che sicuramente $ LHS=2\lfloor a \rfloor + 2\lfloor b \rfloor + 1 $ mentre nell'RHS sicuramente almeno uno (wlog) $ \lfloor 2a \rfloor $ è $ 2\lfloor a \rfloor + 1 $ e invece $ \geq \lfloor 2b \rfloor \geq 2\lfloor b \rfloor $. Quindi $LHS \leq RHS$.

A questo punto per concludere basta applicare questa http://it.wikipedia.org/wiki/Identit%C3 ... e_Polignac chiamando $ \dfrac{m}{p^k} = a, \dfrac{n}{p^k} = b $ e applicando per ogni esponente $k$ la disuguaglianza di sopra. In questo modo $v_p(m!n!(m+n)!) \leq v_p((2m)!(2n)!)$ per ogni $p$ e quindi si ha la divisibilità.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

127

Messaggio da jordan » 22 ott 2012, 13:54

Problema 127 da qui:
bĕlcōlŏn ha scritto:Trova tutti i numeri naturali $n$ per i quali esiste una permutazione $(p_1,p_2,\dots,p_n)$ di numeri $(1,2,\dots,n)$ tale che gli insiemi formati dai numeri $p_i+i \quad \forall 1\leq i \leq n$ e $p_i-i \quad \forall 1\leq i \leq n$ sono sistemi completi di residui modulo $n$.
jordan ha scritto:Definiamo $\sigma_1(i):=p_i+i$ and $\sigma_2(i):=p_i-i$ le due permutazioni di $i$, per ogni $i=1,2,\ldots,n$.

Dal momento che $\{\sigma_1(1),\sigma_1(2),\ldots,\sigma_1(n)\}$, $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e $\{p_1,p_2,\ldots,p_n\}$ sono tre permutazioni di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_1^2(i)+\sigma_2^2(i)} \equiv \sum_{i=1}^n{i^2+i^2}\pmod n$, cioè $\displaystyle 2\sum_{i=1}^n{p_i^2+i^2}\equiv \sum_{i=1}^n{i^2+i^2} \pmod n \implies n \mid 2\sum_{i=1}^n{p_i^2} \equiv \frac{1}{3}n(n+1)(2n+1)$: questo significa che $n$ non è multiplo di $3$.

Dal momento che $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e' una permutazione di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_2(i)} \equiv \sum_{i=1}^n{i} \pmod n$, cioè $n \mid \displaystyle \sum_{i=1}^n{p_i} \equiv \frac{1}{2}n(n+1)$: questo significa che $n$ deve essere dispari.

Assumiamo ora che $\text{gcd}(n,6)=1$ e poniamo $p_i\equiv 2i \pmod n$ per $i=1,2,\ldots,n$ (e' difatti una permutazione visto che $n$ e' dispari). Adesso $\sigma_1(i) \equiv 3i \pmod n$ (e' ancora una permutazione visto che $n$ non è multiplo di $3$) e banalmente $\sigma_2(i)= i$. []

Ps. Bell'esercizio
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

128

Messaggio da jordan » 22 ott 2012, 13:55

Problema 128 da qui:
jordan ha scritto:Sia $f(x)$ un polinomio non costante a coefficienti interi. Sia $S(f(x))$ l'insieme di tutti e soli i primi $p$ tali che esiste $n$ intero con $p\mid f(n)$. Mostrare che $S(f(n))$ non e' finito.

(Schur)
Ido Bovski ha scritto:Sia $\displaystyle f(x)=\sum_{i=0}^m a_ix^i$. Se $a_0=0$, chiaramente $p\mid f(p)$ per ogni $p$ primo. Analizziamo ora il caso in cui $a_0\neq 0$.
L'equazione $f(x)=\pm 1$ ha un numero finito di soluzioni, pertanto $S(f(x))$ non è vuoto. Supponiamo che $S(f(x))$ sia finito e chiamiamo $p_1, p_2,\ldots, p_k$ i suoi elementi. Allora, detto $P=p_1p_2\ldots p_k$, abbiamo che $\displaystyle f(a_0Px)=a_0 \left(1+\sum_{i=1}^m a_ia_0^{i-1}P^ix^i \right)=a_0g(x)$. Per lo stesso ragionamento di prima, esistono $n$ intero e $q$ primo tali che $q\mid g(n)$. Allora $q\mid f(a_0Pn)$, ma ciò è assurdo poiché $q\nmid P$. Dunque, $S(f(x))$ non è finito.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Staffetta tdn

Messaggio da jordan » 22 ott 2012, 13:56

Problema 129 da qui:
Ido Bovski ha scritto:Determinare tutte le soluzioni intere dell'equazione
$$\frac{x^7-1}{x-1}=y^5-1.$$
jordan ha scritto:\[ y^5-1=\frac{x^7-1}{x-1}=1+x(x+1)(x^2+x+1)(x^2-x+1) \]
Dato che $2\mid x(x+1)$ allora
\[ y^5-1\equiv \frac{x^7-1}{x-1} \equiv 1 \pmod 2\]
Abbiamo che $\displaystyle q(x):=\frac{x^7-1}{x-1}$ e' il settimo polinomio ciclotomico con dominio $\mathbb{R}\setminus\{1\}$; ora $q(0)=q(-1)=1$ e $q(2)=2^7-1$, che non sono esprimibili nella forma $y^5-1$; in tutti gli altri casi abbiamo $|x-1|\ge 2$, per cui possiamo definire un primo $p$ tale che $p \mid x-1$.
$\bullet$ Caso 1: $7\nmid x-1$.
In tal caso $\displaystyle \upsilon_p\left(\frac{x^7-1}{x-1}\right)=\upsilon_p(7)=0$, in altre parole se $p\mid x-1$ allora $p\nmid \displaystyle \frac{x^7-1}{x-1}$. Allora $7\mid \text{ord}_p(x) \mid \varphi(p)=p-1$, cioè tutti i primi divisori di $x^7-1$ (e quindi anche di $\displaystyle \frac{x^7-1}{x-1}$) hanno resto $1$ modulo $7$. Abbiamo quindi
\[ \frac{x^7-1}{x-1} \equiv 1 \pmod 7 \implies y^5-1 \equiv 1 \pmod 7 \implies y \equiv 4\pmod 7 \]
Notiamo infine che $y-1 \mid y^5-1 = \frac{x^7-1}{x-1} \mid x^7-1$, per cui anche tutti i divisori primi di $y-1$ sono $\equiv 1 \pmod 7$, i.e. $y-1 \equiv 1 \pmod 7$, assurdo.
$\bullet$ Caso 2: $7\mid x-1$.
Ragionando come sopra, la fattorizzazione canonica di $\displaystyle \frac{x^7-1}{x-1}$ sarà $7 \cdot p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$ dove $p_i\equiv 1 \pmod 7$ per ogni $i=1,2,\ldots,k$; in particolare
\[ \frac{x^7-1}{7(x-1)} \equiv 1 \pmod 7 \]
Dato che $7 \mid \frac{x^7-1}{x-1}$ allora anche $7\mid y^5-1$, ma $\text{gcd}(5,\varphi(7))=1$, per cui anche $7\mid y-1$ (e, vista la fattorizzazione sopra, $7 || y-1$). Esisteranno quindi degli interi $X,Y$ tali che $x=7X+1$ e $y=7Y+1$ (con $7\nmid Y$ e $X\neq 0$). Abbiamo:
\[ \sum_{i=0}^6{(7X+1)^i}=(7Y+1)^5-1 \]
che in $\mathbb{Z}/7^2\mathbb{Z}$ implica
\[ \sum_{i=0}^6{(7iX+1)}=5\cdot 7 Y \implies 7+7X\sum_{i=0}^6{i}=5\cdot 7 Y \implies 7=5\cdot 7 Y\]
cioè $5Y \equiv 1 \pmod 7$, i.e. $Y \equiv 3 \pmod 7$.
D'altra parte sappiamo che $\frac{x^7-1}{7(x-1)} \equiv 1 \pmod 7$ per cui anche $\frac{1}{7}(y^5-1) \equiv 1 \pmod 7 \implies Y=\frac{1}{7}(y-1) \equiv 1 \pmod 7$, assurdo. []
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

130

Messaggio da jordan » 22 ott 2012, 13:57

Problema 130 da qui:
jordan ha scritto:Trovare tutti gli interi positivi $n$ tali che $3^n+4^n \mid 5^n$.
kalu ha scritto:Se $ 4 \mid n $ per Fermat $ 3^n+4^n \equiv 2 \pmod{5} $, assurdo.
Se $ n $ è dispari $ 7 \mid 3^n+4^n \to 7 \mid 5^n $, assurdo.
Quindi $ n $ è della forma $ 2k $, con $ k $ dispari. Allora deve valere $$9^k+16^k=5^z$$ per qualche $ z\leq 2k $.
Suppongo che esista un primo $ q $ tale che $ q \mid k $. Applico allora il lemma LTE: $$\displaystyle v_5\biggl(\frac{9^k+16^k}{9^{\frac{k}{q}}+16^{\frac{k}{q}}}\biggl)=v_5({9^k+16^k})-v_5(9^{\frac{k}{q}}+16^{\frac{k}{q}})=v_5(q)\leq 1$$ Dato che banalmente $ \displaystyle \frac{9^k+16^k}{9^{\frac{k}{q}}+16^{\frac{k}{q}}}>1 $, Deve valere $ q=5 $, e $ \displaystyle \frac{9^k+16^k}{9^{\frac{k}{5}}+16^{\frac{k}{5}}}=5 $.
Noto che: $$\displaystyle\sqrt[5]{\frac{5(9^{\frac{k}{5}}+16^{\frac{k}{5}})}{2}}=\sqrt[5]{\frac{9^k+16^k}{2}}\geq \frac{9^{\frac{k}{5}}+16^{\frac{k}{5}}}{2} \to \frac{9^{\frac{k}{5}}+16^{\frac{k}{5}}}{2} \leq \sqrt[4]{5}$$
Chiaramente assurdo.
Quindi non esistono primi divisori di $ k $: allora $ k=1 $, che in effetti soddisfa.
Concludo che l'unica soluzione è $ n=2 $.
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

131

Messaggio da jordan » 22 ott 2012, 13:58

Problema 131 da qui:
kalu ha scritto:Qualcosa di generale e (credo) utile da risolvere e tenere bene a mente:

a) "Own". Trovare tutte le quintuple $ (a, b, n, p, z) $ di interi positivi, con gcd$ (a, b)=1 $, max$ \{a, b\}>1 $, $ n>1 $ dispari e $ p $ primo, tali che: $$a^n+b^n=p^z$$

b) "Own". Siano $ a, b, n, p, z $ interi positivi con gcd$ (a, b)=1 $, $ n>1 $, $ p $ primo, tali che: $$a^n-b^n=p^z$$ Dimostrare che $ n $ è primo.
Testo nascosto:
In un po' di thread abbastanza recenti potreste trovare più di un hint :!:
Forse basterà risolverne uno per avere il testimone :|
NB Gli "own" sono fra virgolette perchè si tratta di equazioni talmente generali che non si può credere che nessuno ci abbia pensato prima di me xD
jordan ha scritto: $\bullet$ Se $p=2$ siano $\alpha, \beta, A, B$ univocamente determinati tali che $a=2^A\alpha, b=2^B\beta$ e wlog $A\le B$ con $2\nmid \alpha\beta$; abbiamo
\[ 2^z=a^n+b^n=2^{nA}\left(\alpha^n+2^{n(B-A)}\beta^n\right) \]
Se $A\neq B$ allora $\alpha^n+2^{n(B-A)}\beta^n$ e' dispari, maggiore di $1$, e divide $2^z$, assurdo. Resta il caso $A=B$, allora $2^{z-nA}=\alpha^n+\beta^n$ e $z-nA=\upsilon_2(\alpha^n+\beta^n)=\upsilon_2(\alpha+\beta) \le \text{log}_2(\alpha+\beta)$. Per cui:
\[ \alpha^3+\beta^3\le \alpha^n+\beta^n=2^{z-nA}\le 2^{\text{log}_2(\alpha^2-\beta^2)-1} \le \alpha+\beta \implies \alpha=\beta=1 \]
Per cui esistono solo le soluzioni banali $(a,b,n,z)=(2^k,2^k,n,kn+1)$.

$\bullet$ Se $p\ge 3$, dato che $3\le a+b \mid a^n+b^n = p^z$, allora $a+b, a^n+b^n$ sono potenze di $p$. Per LTE:
\[ z=\upsilon_p(p^z)=\upsilon_p(a^n+b^n)=\upsilon_p(a+b)+\upsilon_p(n) \implies a^n+b^n=p^z \le p^{\text{log}_p(a+b)+\text{log}_p(n)}=n(a+b) \]
Per le medie $n(a+b)\ge a^n+b^n > \frac{1}{2^{n-1}}(a+b)^n \implies a+b < 2n^{\frac{1}{n-1}}\le 2\sqrt{3} \implies a+b \le 3$ cioè wlog $a=1, b=2$. Dobbiamo quindi risolvere
\[ 2^n+1=p^z \]
per qualche $n$ dispari $>1$, ma $3\mid 2^n+1^n \implies p=3$. Modulo $4$ abbiamo $z$ pari, per cui $2^n=(3^{\frac{z}{2}}+1)(3^{\frac{z}{2}}-1)$,entrambi i fattori sono potenze di $2$ e differiscono di $2$, per cui devono essere $2$ e $4$ da cui $z=2$. Da cui l'unica soluzione $2^3+1^3=3^2$. []
The only goal of science is the honor of the human spirit.

Rispondi