Mostrare che per ogni coppia di interi positivi a,b esiste un irrazionale x tale che
\[ \lfloor x^n \rfloor \equiv a \pmod b \]
per ogni intero positivo n.
$\lfloor x^n \rfloor \equiv a \pmod b$
$\lfloor x^n \rfloor \equiv a \pmod b$
The only goal of science is the honor of the human spirit.
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: $\lfloor x^n \rfloor \equiv a \pmod b$
Ma anche up! Per come l'ho (forse) risolto io c'è una soluzione truccosissima!
Re: $\lfloor x^n \rfloor \equiv a \pmod b$
In effetti questo era davvero un bel problema. Com'è la tua?
The only goal of science is the honor of the human spirit.
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: $\lfloor x^n \rfloor \equiv a \pmod b$
Io dimostro che il numero di soluzioni di quella roba non è numerabile.
Per farlo considero l'intervallo $[3b+a;3b+a+1)$ e dimostro per induzione su $k$ che riesco a trovare due "sottointervalli" disgiunti che soddisfano per ogni $1 \le n \le k$: se supponiamo che esiste un $x$ tale che $\lfloor x^n \rfloor \equiv a \pmod{b}$, poiché $x$ sta nell'intervallo $[3b+a;3b+a+1)$, $x^{k+1}$ può variare in un intervallo che passa per almeno $3b+a$ reali; pertanto è possibile trovare due intervalli $l$ tali che $x^{k+1} \in l; x^{k+1} \equiv a \pmod{b}$; l'intervallo $l$, per ipotesi induttiva, soddisfa anche gli altri $n$. Poiché posso trovare sottointervalli di sottointervalli un numero arbitrariamente grande di volte, esiste effettivamente un numero $g$ che soddisfa la condizione del testo. Quanti sono questi numeri? Almeno uno per ogni modo di scegliere i sottointervalli. Ma, fissato un sottointervallo, posso scegliere il sottointervallo successivo in $2$ modi. È pertanto possibile mettere in biezione i vari $g$ con una stringa infinita di $01001111011100101101...$, dove $0$ indica l'intervallo minore e $1$ l'intervallo maggiore. Poiché queste stringhe non sono numerabili, non possono essere messe in biezione con i numeri razionali, pertanto i vari $g$ non possono essere messi in biezione con i numeri razionali, pertanto esiste un $g$ non razionale che soddisfa.
Per farlo considero l'intervallo $[3b+a;3b+a+1)$ e dimostro per induzione su $k$ che riesco a trovare due "sottointervalli" disgiunti che soddisfano per ogni $1 \le n \le k$: se supponiamo che esiste un $x$ tale che $\lfloor x^n \rfloor \equiv a \pmod{b}$, poiché $x$ sta nell'intervallo $[3b+a;3b+a+1)$, $x^{k+1}$ può variare in un intervallo che passa per almeno $3b+a$ reali; pertanto è possibile trovare due intervalli $l$ tali che $x^{k+1} \in l; x^{k+1} \equiv a \pmod{b}$; l'intervallo $l$, per ipotesi induttiva, soddisfa anche gli altri $n$. Poiché posso trovare sottointervalli di sottointervalli un numero arbitrariamente grande di volte, esiste effettivamente un numero $g$ che soddisfa la condizione del testo. Quanti sono questi numeri? Almeno uno per ogni modo di scegliere i sottointervalli. Ma, fissato un sottointervallo, posso scegliere il sottointervallo successivo in $2$ modi. È pertanto possibile mettere in biezione i vari $g$ con una stringa infinita di $01001111011100101101...$, dove $0$ indica l'intervallo minore e $1$ l'intervallo maggiore. Poiché queste stringhe non sono numerabili, non possono essere messe in biezione con i numeri razionali, pertanto i vari $g$ non possono essere messi in biezione con i numeri razionali, pertanto esiste un $g$ non razionale che soddisfa.