omega(2^(4x+2)+1)<3

[jordan]

Trovare tutti gli $ x \in \mathbb{N} $ tali che $ \omega(2^{4x+2}+1)<3 $.


Nb. Qui $ \omega(n):=|\{p \in \mathbb{P}: p \mid n\}| $

[<enigma>]

La prima cosa da fare è riscrivere l'espressione come $ 4^{2x+1}+1=(2^{2x+1}+2^{x+1}+1)(2^{2x+1}-2^{x+1}+1) $. L'espressione è sempre divisibile per 5 e 5 è fattore di uno o dell'altro, non di entrambi perché se x=0 o 3 (mod 4) puoi verificare che solo uno dei fattori è divisibile per 5, e simmetricamente se x=1 o 2 (mod 4) l'altro è divisibile per 5.
Per mostrare che ha piu' di due fattori, prendi il primo e poni per assurdo che sia uguale a $ 5^k $: moltiplicando ambo i membri per $ 2^k $ hai $ 2^k\cdot(2^{2x+1}+2^{x+1}+1)=5^k\cdot2^k, 2^{2x+1+k}+2^{x+1+k}+2^k=10^k $: vedi che il membro a sinistra è esattamente una rappresentazione binaria. Gli unici 1 che compaiono nella rappresentazione binaria della potenza di 10 sono quindi quelli in 2x+1+k-esima posizione, in x+1+k-esima posizione e in k-esima posizione, tutti gli altri sono zeri. Ma si hanno meno di tre cifre uno solo nella rappresentazione binaria di $ 10^0, 10^1 $ e $ 10^2 $, quindi negli altri i fattori sono piu' di due. Soluzione: x=0, 1, 2.

[jordan]

Ciao enigma, e innanzitutto benvenuto nel forum!

La prima cosa da fare è riscrivere l'espressione come $ 4^{2x+1}+1=(2^{2x+1}+2^{x+1}+1)(2^{2x+1}-2^{x+1}+1) $.

Fin qui Ok

L'espressione è sempre divisibile per 5 e 5 è fattore di uno o dell'altro, non di entrambi perché se x=0 o 3 (mod 4) puoi verificare che solo uno dei fattori è divisibile per 5, e simmetricamente se x=1 o 2 (mod 4) l'altro è divisibile per 5.

Questo è facile, ma non l'hai spiegato: perchè prendi le $ x $ modulo 4 quando vuoi verificare la divisibilità per $ 5 $?

Per mostrare che ha piu' di due fattori, prendi il primo...

Questo è meno facile: perchè prendi il primo? Il tuo discorso successivo non mi pare simmetrico con il secondo fattore

..e poni per assurdo che sia uguale a $ 5^k $: moltiplicando ambo i membri per $ 2^k $ hai $ 2^k\cdot(2^{2x+1}+2^{x+1}+1)=5^k\cdot2^k, 2^{2x+1+k}+2^{x+1+k}+2^k=10^k $: vedi che il membro a sinistra è esattamente una rappresentazione binaria.

Ciò che dici non è molto corretto: tutti i numeri in $ \mathbb{R} $ hanno esattamente una rappresentazione binaria..comunque, andiamo avanti

Gli unici 1 che compaiono nella rappresentazione binaria della potenza di 10 sono quindi quelli in 2x+1+k-esima posizione, in x+1+k-esima posizione e in k-esima posizione, tutti gli altri sono zeri.

Qui sembra ok, ma poi scrivi:

..Ma si hanno meno di tre cifre uno solo nella rappresentazione binaria di $ 10^0, 10^1 $ e $ 10^2 $, quindi negli altri i fattori sono piu' di due.

Mo' ferma: perchè mai dovrebbe essere vera questa affermazione?

Oltretutto, ammettendo che tu avessi ipoteticamente dimostrato che $ \omega(2^{2x+1}+2^{x+1}+1) \ge 2 $ (quando è divisibile per 5), e ammettiamo anche che sia vero anche per l'altro caso: questo non implica certo che $ \omega(2^{4x+2}+1) \le 2 $ solo se $ x \in \{0,1,2\} $.

[<enigma>]

Riscrivo la risposta in modo da non lasciare spazio a dubbi.
La scomposizione $ 2^{4x+2}+1=(2^{2x+1}+2^{x+1}+1)(2^{2x+1}-2^{x+1}+1) $ è indiscutibilmente vera per comodità di esposizione dopo (chiamo il primo fattore $ p $ e il secondo $ q $). Dopodiché, prendendo le x mod 4:
se x mod 4=0 allora $ 2^{2x+1}+2^{x+1}+1 $ è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ no;
se x=1 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ non è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ sì;
se x=2 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ non è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ sì;
se x=3 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ no.
A questo punto abbiamo dimostrato che quando uno dei fattori è divisibile per 5 o è una potenza di 5 l'altro non lo è.
Riassumendo: -caso 1, $ p $ potenza di 5 e $ q $ potenza di un primo; -caso 2: $ p $ potenza di 5 e $ q $ prodotto di due o più potenze di primi; -caso 3: $ p $ prodotto di potenza di 5 e di una o più altre potenze di primi e $ q $ potenza di un primo; -caso 4: $ p $ prodotto di una potenza di 5 e di una o più potenze di altri primi e $ q $ prodotto di due o più potenze di altri primi. I casi 2 e 4 hanno sempre più di due fattori e si possono quindi escludere. Rimangono da dimostrare i casi 1 e 3. Lo farò in un altro post (un caso alla volta) se avrai la pazienza di aspettare.

[jordan]

...Dopodiché, prendendo le x mod 4:
se x mod 4=0 allora $ 2^{2x+1}+2^{x+1}+1 $ è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ no;
se x=1 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ non è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ sì;
se x=2 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ non è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ sì;
se x=3 mod 4 allora $ 2^{2x+1}+2^{x+1}+1 $ è divisibile per 5 e $ 2^{2x+1}-2^{x+1}+1 $ no.
A questo punto abbiamo dimostrato che quando uno dei fattori è divisibile per 5 o è una potenza di 5 l'altro non lo è.

Ti ripeto la domanda di prima: ancora NON ci hai spiegato perchè prendile variabili modulo 4, nè perchè prendendo una classe di resto modulo 4 sulla variabile x, allora il residuo in Z/5Z è costante, ed esattamente uno nullo.

Riassumendo: -caso 1, $ p $ potenza di 5 e $ q $ potenza di un primo; -caso 2: $ p $ potenza di 5 e $ q $ prodotto di due o più potenze di primi; -caso 3: $ p $ prodotto di potenza di 5 e di una o più altre potenze di primi e $ q $ potenza di un primo; -caso 4: $ p $ prodotto di una potenza di 5 e di una o più potenze di altri primi e $ q $ prodotto di due o più potenze di altri primi. I casi 2 e 4 hanno sempre più di due fattori e si possono quindi escludere. Rimangono da dimostrare i casi 1 e 3. Lo farò in un altro post (un caso alla volta) se avrai la pazienza di aspettare.

Bè, aspettiamo quindi che inizi a risolvere il problema..

[TBPL]

Be', visto che non posta i risultati del contest, stupriamo i problemi di jordan...

1. $ 5\mid 2^{4x+2}+1 $, in quanto $ 2^{4x+2}+1\equiv 4^{2x+1}+1\equiv {(-1)}^{2x+1}+1\equiv -1+1\equiv 0 \pmod{5} $
2. Se $ 25\mid 2^{4x+2}+1 $, devo avere che $ x\equiv 2 \pmod5 $ (in quanto $ ord_{25}(4)=10 $), ossia che $ 5\mid{4x+2} $. Quindi $ 2^{4x+2}+1=(4^{\frac{2x+1}{5}}+1)((4^{\frac{2x+1}{5}})^4-\cdots+1) $, ma questo significa che c'è un fattore diverso da $ 41 $ che divide $ 2^{4x+2}+1 $...
3. $ 2^{4x+2}+1=(2^{2x+1}+2^{x+1}+1)(2^{2x+1}-2^{x+1}+1) $. Ho che $ gcd(2^{2x+1}+2^{x+1}+1,2^{2x+1}-2^{x+1}+1)=1 $. So che $ 5\mid 2^{4x+2}+1 $ ma $ 25\nmid 2^{4x+2}+1 $. Quindi, se $ 2^{2x+1}+2^{x+1}+1>5 $, ossia se $ x\ge2 $, ho che $ (2^{2x+1}-2^{x+1}+1)>1 $ e che esiste $ p\neq5 $ tale che $ p\mid2^{2x+1}+2^{x+1}+1 $, quindi $ \omega(2^{4x+2}+1)\ge3 $. Per $ x=0 $ ho che $ 2^{4x+2}+1=5 $ e per $ x=1 $ ho che $ 2^{4x+2}+1=65=5\cdot13 $, quindi $ 0,1 $ sono le uniche soluzioni.
Edit: Ah, il punto 2 funziona per i multipli di $ 4^5+1 $, ma non per $ 4^5+1 $ e quindi $ x=2 $, di cui mi stavo dimenticando l'esistenza

[<enigma>]

Ci dev'essere per forza un motivo? Se la funzione è una potenza di 4 ($ 4^{2x+1}+1 $ io ho preso i mod 4. Se vuoi lo faccio anche con i mod 8 o qualche altro, non penso cambi qualcosa. Inoltre ho provato e non ci sono riuscito: puoi anche lasciar perdere la mia idea. Curiosamente sei assai pronto a fare le pulci fino all'ultimo alle dimostrazioni altrui ma quando si tratta di risposte tue va tutto bene ( http://it.answers.yahoo.com/question/in ... 740AAAZVxO : notare che sul polinomio hai scritto due righe senza spiegare un minimo della teoria che ci sta dietro ), quindi se ti dà fastidio che io tenti di rispondere quando per giorni nessun altro si neanche anche degnato di guardare il tuo problema, figurarsi risponderci, non lo farò più; hai solo da dirlo. Saluti

[jordan]

Be', visto che non posta i risultati del contest, stupriamo i problemi di jordan...

Credo ci vorrà ancora qualche giorno..

2. Se $ 25\mid 2^{4x+2}+1 $, devo avere che $ x\equiv 2 \pmod5 $ (in quanto $ ord_{25}(4)=10 $), ossia che $ 5\mid{4x+2} $. Quindi $ 2^{4x+2}+1=(4^{\frac{2x+1}{5}}+1)((4^{\frac{2x+1}{5}})^4-\cdots+1) $, ma questo significa che c'è un fattore diverso da $ 41 $ che divide $ 2^{4x+2}+1 $.
[...]Edit: Ah, il punto 2 funziona per i multipli di $ 4^5+1 $, ma non per $ 4^5+1 $ e quindi $ x=2 $, di cui mi stavo dimenticando l'esistenza

Ci chiarisci solo da dove esce il 41?

3. $ 2^{4x+2}+1=(2^{2x+1}+2^{x+1}+1)(2^{2x+1}-2^{x+1}+1) $. Ho che $ gcd(2^{2x+1}+2^{x+1}+1,2^{2x+1}-2^{x+1}+1)=1 $. So che $ 5\mid 2^{4x+2}+1 $ ma $ 25\nmid 2^{4x+2}+1 $. Quindi, se $ 2^{2x+1}+2^{x+1}+1>5 $, ossia se $ x\ge2 $, ho che $ (2^{2x+1}-2^{x+1}+1)>1 $ e che esiste $ p\neq5 $ tale che $ p\mid2^{2x+1}+2^{x+1}+1 $, quindi $ \omega(2^{4x+2}+1)\ge3 $. Per $ x=0 $ ho che $ 2^{4x+2}+1=5 $ e per $ x=1 $ ho che $ 2^{4x+2}+1=65=5\cdot13 $, quindi $ 0,1 $ sono le uniche soluzioni.

Ok, il terzo punto very good, anche più facile della mia, che allego sotto

$ 2^{4m + 2} + 1 $ is in the form $ x^4 + 4y^4 $ (Sophie-German identity), so it can be factorized as $ ((2^m)^2 + (2^m - 1)^2)((2^m)^2 + (2^m + 1)^2) $. Since the two factor are coprime,both odd and greater than 1 then we are lead to solve the system $ p^a = (2^m)^2 + (2^m + 1)^2 > (2^m)^2 + (2^m - 1)^2 = q^b $, for some distinct prime $ p,q $ (for istance $ 4 \mid \text{gcd}(p - 1,q - 1) $ since $ 1 = (\frac { - 1}{p}) = (\frac { - 1}{q}) $) and $ a,b $ are positive integers. Now we have three consecutive quadratic residue of (x-1)²,x²,(x+1)², where x² is non zero for every mod p>2. Modulo 5 we see that if x² is a fixed r in {-1,1} then at least one between (x-1)² and (x+1)² is -r. It means that (p-5)(q-5)=0. So, in other words, it sufficies to find all solutions of the equation $ (2^m)^2 + (2^m + \ell)^2 = 5^a $, where $ l \in \{ - 1,1\} \text{ and } a \in \mathbb{N}_0 $. If $ m > 1 $ we can see modulo 8 that $ 2 \mid a $, so it exists $ b \in \mathbb{N}_0 $ such that $ a = 2b $, so $ 2^{2m} = (5^b + 2^m + \ell)(5^b - 2^m - \ell) $. Now $ \text{gcd}(5^b + 2^m + \ell,5^b - 2^m - \ell) $ $ = \text{gcd}(5^b + 2^m + \ell,2 \cdot 5^b) $ and must be 2, so it sufficies to solve $ 2^{2m - 1} = 5^b + 2^m + \ell \text{ and } 2 = 5^b - 2^m - \ell $ $ \implies 5^b = 2^m + \ell + 2 = 2^{2m - 1} - 2^m - \ell $. It implies that $ 2^{2m - 1} = 2^{m + 1} + 2\ell + 2 \le 2^{m + 1} + 4 $ that is false if m > 2. So, unique solutions are $ m \in \{0,1,2\} $ that is verified by hand.[]

Ok, passiamo ad enigma:

Ci dev'essere per forza un motivo? Se la funzione è una potenza di 4 ($ 4^{2x+1}+1 $ io ho preso i mod 4. Se vuoi lo faccio anche con i mod 8 o qualche altro, non penso cambi qualcosa. Inoltre ho provato e non ci sono riuscito: puoi anche lasciar perdere la mia idea.

LOL Guarda che esiste il motivo perchè il mod 4 va bene

Curiosamente sei assai pronto a fare le pulci fino all'ultimo alle dimostrazioni altrui ma quando si tratta di risposte tue va tutto bene ( http://it.answers.yahoo.com/question/in ... 740AAAZVxO : notare che sul polinomio hai scritto due righe senza spiegare un minimo della teoria che ci sta dietro )

Per me ho scritto anche abbastanza visto la banalità di quei problemi, e non mi pare che ci fosse qualcosa di equivoco o campato per aria.

..quindi se ti dà fastidio che io tenti di rispondere quando per giorni nessun altro si neanche anche degnato di guardare il tuo problema, figurarsi risponderci, non lo farò più; hai solo da dirlo. Saluti

A me fa piacere che qualcuno risponda, anzi..solo non capisco perchè ti stai indirizzando su questo tono; ti ho solo fatto notare delle imprecisioni, se poi vuoi sentirti dire che è tutto ok è un altro discorso..

[<enigma>]

Non voglio sentirmi dire che è tutto ok, anzi le critiche sono ben accette. Facciamo che ci provo una volta ancora poi altrimenti lascio perdere. Ah, mi potresti spiegare una cosa: com'è che quando io ti dissi che se $ 25|2^{4x+2}+1 $ allora per forza x=2 (mod 5) tu mi rispondesti (testuali parole) "no, no, dimostrala come vuoi, basta solo che non applichi quello agli esponenti perché oltre ad essere brutto è anche sbagliato", e adesso che lo dice TBPL (con tutto il rispetto per lui e per te) va bene? Così non mi faciliti certo il lavoro... Saluti

[TBPL]

Ci chiarisci solo da dove esce il 41? Surprised

Se il motivo è filosofico, allora poteva essere anche $ 4999 $, non sarebbe cambiato nulla
Se invece devo spiegare perché, è solo casoso:
Mettiamo che $ 41\cdot5\mid4^{\frac{2x+1}{5}}+1 $. Allora l'altro fattore deve essere una potenza di $ 5 $, ma è $ 5\pmod25 $ (provare il contaccio per credere...), quindi questo avviene raramente. Ed è facile convincersi che $ 4^{\frac{2x+1}{5}}+1 $ è una potenza di $ 41 $ o di $ 5 $ abbastanza raramente...

Non voglio sentirmi dire che è tutto ok, anzi le critiche sono ben accette. Facciamo che ci provo una volta ancora poi altrimenti lascio perdere. Ah, mi potresti spiegare una cosa: com'è che quando io ti dissi che se $ 25|2^{4x+2}+1 $ allora per forza x=2 (mod 5) tu mi rispondesti (testuali parole) "no, no, dimostrala come vuoi, basta solo che non applichi quello agli esponenti perché oltre ad essere brutto è anche sbagliato", e adesso che lo dice TBPL (con tutto il rispetto per lui e per te) va bene? Così non mi faciliti certo il lavoro... Saluti

$ ord_{25}(4)=10 $ può essere un modo carino per dire "fatevi tutti i casi, che io non ho voglia" . Sapendo un po' più di teoria, questo implica che se $ x\equiv\frac{10}{2}\pmod{10} $, allora $ 4^x\equiv-1\pmod{25} $. Gli esponenti non si comportano sempre bene, modulo roba... Esempio: prova a vedere cosa fanno le potenze di $ 4 $ modulo $ 5 $ guardando l'esponente modulo $ 3 $...
Se poi hai dei dubbi, sono disposto a chiarire

[jordan]

Ah, mi potresti spiegare una cosa: com'è che quando io ti dissi che se $ 25|2^{4x+2}+1 $ allora per forza x=2 (mod 5) tu mi rispondesti (testuali parole) "no, no, dimostrala come vuoi, basta solo che non applichi quello agli esponenti perché oltre ad essere brutto è anche sbagliato", e adesso che lo dice TBPL (con tutto il rispetto per lui e per te) va bene?

TBPL sapeva il perchè valeva "per forza", a differenza te non ti davi ragione del perchè a volte usi i mod 4 e i mod 5 agli esponenti.. Oltretutto una casistica completa è sempre accettata.
@i lettori della soluzione di TBPL: è stato usato in modo implicito ( ) il fatto che se $ (x,p) \in \mathbb{Z} \times \mathbb{P} $ allora $ \text{gcd}(x+1,\phi_p(x)) \mid p $..

[<enigma>]

Ho scoperto adesso che quella è una fattorizzazione aurifeuilliana! Ecco dove l'avevo già vista!

[jordan]

E' l'identità di Sophie-German ..

Comunque su google

La ricerca di - aurifeuilliana - non ha prodotto risultati in nessun documento.

Suggerimenti:

Assicurarsi che tutte le parole siano state digitate correttamente.
Provare con parole chiave diverse.
Provare con parole chiave più generiche.

[<enigma>]

http://en.wikipedia.org/wiki/Aurifeuill ... torization