Discussione:
Giochino 71
(troppo vecchio per rispondere)
El Filibustero
2020-12-18 14:02:47 UTC
Permalink
Dimostrare che, qualunque sia n,

1024^n + 32^n + 1

non e' un numero primo. Ciao
El Filibustero
2020-12-18 16:49:25 UTC
Permalink
Post by El Filibustero
Dimostrare che, qualunque sia n,
1024^n + 32^n + 1
non e' un numero primo.
qualunque n intero positivo, beninteso.
effe
2020-12-19 10:55:21 UTC
Permalink
Post by El Filibustero
Post by El Filibustero
Dimostrare che, qualunque sia n,
1024^n + 32^n + 1
non e' un numero primo.
qualunque n intero positivo, beninteso.
2^(10n)+2^(5n)+1= A*B
A=[2^(2n)+2^n+1]
B=[ 2^(8n)-2^(7n)+2^(5n)-2^(4n)+2^(3n)-2^n+1]

pongo 2^n=a
(a^5)^2+a^5+1=[(a^5)^3-1]/[a^5-1]=[(a^3)^5-1]/[a^5-1]=
=[a^3-1]*[(a^3)^4+(a^3)^3+(a^3)^2+a^3+1]/[(a-1)*(a^4+a^3+a^2+a+1)]=
=[a^2+a+1]*[a^12+a^9+a^6+a^3+1]/[a^4+a^3+a^2+a+1]=
=[a^2+a+1]*[ a^8-a^7+a^5-a^4+a^3-a+1]
El Filibustero
2020-12-19 12:37:39 UTC
Permalink
Post by effe
2^(10n)+2^(5n)+1= A*B
A=[2^(2n)+2^n+1]
B=[ 2^(8n)-2^(7n)+2^(5n)-2^(4n)+2^(3n)-2^n+1]
Esatto. Rilancio: dimostrare che se x^(2n) + x^n + 1 e' primo allora n
e' una potenza di 3. Ciao
effe
2020-12-19 14:41:33 UTC
Permalink
Post by El Filibustero
Esatto. Rilancio: dimostrare che se x^(2n) + x^n + 1 e' primo allora n
e' una potenza di 3. Ciao
E' lecito partire da quanto dimostrato prima, supponendo che in generale
sia x^(2n)+x^n+1=[x^2+x+1]*[ x^(2n-2)-x^(2n-3)...-x+1] e dimostrando
poi che per n=3^k non può essere vero? In questo caso un'idea ce l'avrei.
Ciao
El Filibustero
2020-12-19 15:04:06 UTC
Permalink
Post by effe
Post by El Filibustero
Esatto. Rilancio: dimostrare che se x^(2n) + x^n + 1 e' primo allora n
e' una potenza di 3. Ciao
E' lecito partire da quanto dimostrato prima, supponendo che in generale
sia x^(2n)+x^n+1=[x^2+x+1]*[ x^(2n-2)-x^(2n-3)...-x+1] e dimostrando
poi che per n=3^k non può essere vero?
Guasi. Non e' vero nemmeno per n=6, ad esempio. Hint: in modulo
yy+y+1, quante potenze distinte di y ci sono? Poche. Ciao
effe
2020-12-19 16:03:00 UTC
Permalink
Post by El Filibustero
Post by effe
E' lecito partire da quanto dimostrato prima, supponendo che in generale
sia x^(2n)+x^n+1=[x^2+x+1]*[ x^(2n-2)-x^(2n-3)...-x+1] e dimostrando
poi che per n=3^k non può essere vero?
Guasi. Non e' vero nemmeno per n=6, ad esempio. Hint: in modulo
yy+y+1, quante potenze distinte di y ci sono? Poche. Ciao
Sì, poche, una.

y^2+y+1 ha come soluzioni a=-1/2+i*1/2rad(3) e
b= -1/2-i*1/2rad(3) di modulo 1 come tutte le loro potenze.
a=e^(i*2pi/3)
b=e^(i*pi/3)

a^(2n)+a^n+1=e^(i*n*4pi/3)+e^(i*n*2pi/3)+1=
=-1/2-i*1/2rad(3)-1/2+i/1/2rad(3)+1=0 se n=1
=-1/2+i*1/2rad(3)-1/2-i/1/2rad(3)+1=0 se n=2
=1+1+1 se n=3 oppure n=multiplo di 3
Lo stesso per b.
Segue che y^(2n)+y^n+1 ha come fattore y^2+y+1 in quanto sia a che b
sono soluzioni. Ma se n=3k non è scomponibile.
Quindi che n sia potenza di 3 è restrittivo?
effe
2020-12-19 17:24:21 UTC
Permalink
Il 19/12/2020 17.03, effe ha scritto:

ops
b=e^(i*4pi/3)
El Filibustero
2020-12-19 17:32:07 UTC
Permalink
Post by effe
Post by El Filibustero
Guasi. Non e' vero nemmeno per n=6, ad esempio. Hint: in modulo
yy+y+1, quante potenze distinte di y ci sono? Poche. Ciao
Sì, poche, una.
Non esageriamo. Siamo nell'ambito dei polinomi Z[x] sull'anello Z
degli interi...
Post by effe
y^2+y+1 ha come soluzioni a=-1/2+i*1/2rad(3) e
b= -1/2-i*1/2rad(3) di modulo 1 come tutte le loro potenze.
a=e^(i*2pi/3)
b=e^(i*pi/3)
... niente fattorizzazioni complesse. Quante potenze di 2 in modulo
2*2+2+1=7?
Post by effe
Segue che y^(2n)+y^n+1 ha come fattore y^2+y+1 in quanto sia a che b
sono soluzioni. Ma se n=3k non è scomponibile.
non e' scomponibile in Z[x].
Post by effe
Quindi che n sia potenza di 3 è restrittivo?
Non e' restrittivo, perche' se n contiene fattori diversi da 3...
Hint: provare che

x^(2*3^k*q) + x^(3^k*q) + 1

[con q coprimo con 3] e' divisibile per x^(2*3^k) + x^(3^k) + 1. Ciao
El Filibustero
2020-12-19 17:42:13 UTC
Permalink
Post by El Filibustero
Post by effe
Segue che y^(2n)+y^n+1 ha come fattore y^2+y+1 in quanto sia a che b
sono soluzioni. Ma se n=3k non è scomponibile.
non e' scomponibile in Z[x].
Mi correggo: volevo dire che y^(2n)+y^n+1 con n=3k e' generalmente
scomponibile in Z[x] (vedi hint), ma non ha yy+y+1 come fattore. Ciao
effe
2020-12-19 19:53:46 UTC
Permalink
Post by El Filibustero
Non esageriamo. Siamo nell'ambito dei polinomi Z[x] sull'anello Z
degli interi...
E' un argomento che devo rivedermi.
Post by El Filibustero
... niente fattorizzazioni complesse. Quante potenze di 2 in modulo
2*2+2+1=7?
Non avevo assolutamente capito a cosa ti riferivi.
E dubito di avere capito adesso.
2^0, 2^1 e 2^2?
Post by El Filibustero
Non e' restrittivo, perche' se n contiene fattori diversi da 3...
Hint: provare che
x^(2*3^k*q) + x^(3^k*q) + 1
[con q coprimo con 3] e' divisibile per x^(2*3^k) + x^(3^k) + 1. Ciao
Ci penso.
Post by El Filibustero
volevo dire che y^(2n)+y^n+1 con n=3k e' generalmente
scomponibile in Z[x] (vedi hint), ma non ha yy+y+1 come fattore.
Infatti era l'ipotesi che mi chiedevo se fosse lecita. Ciao

Ciao
El Filibustero
2020-12-19 20:24:21 UTC
Permalink
Post by effe
Non avevo assolutamente capito a cosa ti riferivi.
E dubito di avere capito adesso.
2^0, 2^1 e 2^2?
Esatto, sono tre potenze distinte. Cambia qualcosa se invece di 2 c'e'
un altro numero? Hint: e se questo numero fosse uguale a x^(3^k)? Ciao
effe
2020-12-20 08:24:12 UTC
Permalink
Post by El Filibustero
Esatto, sono tre potenze distinte. Cambia qualcosa se invece di 2 c'e'
un altro numero? Hint: e se questo numero fosse uguale a x^(3^k)? Ciao
Sì, ho capito, ma la formalizzazione mi riesce difficile.
Post by El Filibustero
(x^(2a)+x^a+1)=[x^2+x+1]*A/B
con A=[x^(3(a-1))+x^(3*(a-2))+...+x^3+1]
e B=[x^(a-1)+x(a-2)+...+x+1])

A=(x^(2*3)+x^3+1)*(x^(2*3^2)+x^(3^2)+1)*...*(x^(2a)+x^a+1)
B=(x^2+x+1)*(x^(2*3)+x^3+1)*...*(x^(a-1)+...+1)
per cui al numeratore resta (x^(2a)+x^a+1)
e al denominatore (x^2+x+1)
e quindi abbiamo [x^2+x+1]*(x^(2a)+x^a+1)/(x^2+x+1)
Cioè non si scompone e quindi è primo.
Non riesco a vedere la divisione se non con tentativi. Ciao
El Filibustero
2020-12-20 21:49:59 UTC
Permalink
Post by effe
Post by El Filibustero
(x^(2a)+x^a+1)=[x^2+x+1]*A/B
con A=[x^(3(a-1))+x^(3*(a-2))+...+x^3+1]
e B=[x^(a-1)+x(a-2)+...+x+1])
A=(x^(2*3)+x^3+1)*(x^(2*3^2)+x^(3^2)+1)*...*(x^(2a)+x^a+1)
B=(x^2+x+1)*(x^(2*3)+x^3+1)*...*(x^(a-1)+...+1)
per cui al numeratore resta (x^(2a)+x^a+1)
e al denominatore (x^2+x+1)
e quindi abbiamo [x^2+x+1]*(x^(2a)+x^a+1)/(x^2+x+1)
Cioè non si scompone e quindi è primo.
Piu' che all'irriducibilita' di x^(2*3^k)+x^(3^k)+1 penserei piuttosto
al fatto che x^(2*3^k*q)+x^(3^k*q)+1 con q non multiplo di 3 ammette
una scomposizione in fattori non banali [hint: uno dei quali e'
x^(2*3^k)+x^(3^k)+1], perche' cio' comporta che se x^(2n)+x^n+1 e'
primo, allora necessariamente n e' una potenza di 3. Ciao
effe
2020-12-21 16:23:36 UTC
Permalink
Post by El Filibustero
Piu' che all'irriducibilita' di x^(2*3^k)+x^(3^k)+1 penserei piuttosto
al fatto che x^(2*3^k*q)+x^(3^k*q)+1 con q non multiplo di 3 ammette
una scomposizione in fattori non banali [hint: uno dei quali e'
x^(2*3^k)+x^(3^k)+1], perche' cio' comporta che se x^(2n)+x^n+1 e'
primo, allora necessariamente n e' una potenza di 3. Ciao
Ecco, finalmente la montagna ha partorito il topolino!
Ho scomposto di tutto dando a k e q vari valori: 2, 3, 4, 5.
E c'era sempre quel fattore x^(2*3^k)+x^(3^k)+1.
Cazzarola, finalmente ho capito! Basta imporre che quello sia l'unico
fattore, visto che è irriducibile. Occorre che il fattore q venga
incorporato in 3^k ossia che q sia, a sua volta, una potenza di 3.
Allora se il trinomio è irriducibile -> n=3^p e se n=3^p-> il trinomio è
irriducibile. Grazie. Ciao
Massimo Grazzini
2020-12-24 20:16:30 UTC
Permalink
Salve a tutti, mi intrometto perché trovo la questione della riducibilità dei polinomi in Z molto avvincente (anche se su di essa so abbastanza poco).

Con un po' di pazienza si dovrebbe poter provare che

x^2n + x^ + 1 è divisibile per:
a) x^2 + x + 1 se n mod 3 = 2;
b) x^2 - x + 1 se n mod 3 = 1.
Inoltre:
c) x^2n + x^n + 1 in Z non ammette altri divisori monici di secondo grado oltre a quelli indicati sopra;
d) se n è un multiplo di 3, allora x^2n + x^n + 1 non è divisibile né per x^2 + x + 1, né per x^2 - x + 1.

E' corretto?
Post by El Filibustero
Hint: provare che
x^(2*3^k*q) + x^(3^k*q) + 1
[con q coprimo con 3] e' divisibile per x^(2*3^k) + x^(3^k) + 1
In effetti il risultato sopra non esclude che x^2n + x^n + 1 con n multiplo di tre possa ammettere divisori di grado superiore al secondo...

Proverò ad applicarmici

Massimo
Massimo Grazzini
2020-12-24 20:57:27 UTC
Permalink
Post by El Filibustero
Hint: provare che
x^(2*3^k*q) + x^(3^k*q) + 1
[con q coprimo con 3] e' divisibile per x^(2*3^k) + x^(3^k) + 1
Sì, è ovvio, se q >= 2 e non divisibile per tre allora il polinomio y^2q + y^q + 1, ammette uno almeno tra divisori y^2 + y + 1 e y^2 - y + 1.

y = x^(3^k), si conclude che x^(2*3^k*q) + x^(3^k*q) + 1 ammette x^(2*3^k) + x^(3^k) + 1 o x^(2*3^k) - x^(3^k) + 1 come divisore.

Per altro, se q è pari (dunque q = 2s), si ha anche la fattorizzazione

x^(2*3^k*q) + x^(3^k*q) + 1 = [x^(q*3^k)]^2 + 2 x^(q*3^k) + 1 - [x^(s*3^k)]^2 = [x^(q*3^k) + 1]^2 - [x^(s*3^k)]^2 =
= [x^(q*3^k) + 1 - x^(s*3^k)]*[x^(q*3^k) + 1 + x^(s*3^k)] = [x^(2*s*3^k) - x^(s*3^k) + 1]*[x^(2*s*3^k) + x^(s*3^k) + 1].

Massimo
El Filibustero
2020-12-26 14:31:45 UTC
Permalink
Post by Massimo Grazzini
Con un po' di pazienza si dovrebbe poter provare che
a) x^2 + x + 1 se n mod 3 = 2;
b) x^2 - x + 1 se n mod 3 = 1.
La situazione in generale e' la seguente. Supponiamo n=q*3^k (non
banalmente nullo), con q coprimo con 3.

caso 1. q=1, o sia n e' la k-esima potenza di 3. Allora x^(2n)+^n+1 e'
irriducibile sui razionali, in quanto 3^(k+1)-esimo polinomio
ciclotomico.

caso 2. q=1 (mod 3), o sia q=3h+1. Posto y=x^(3^k),
x^(2n)+x^n+1=y^(2q)+y^q+1 e' il prodotto di

yy+y+1 (non di yy-y+1)

e di

y^(2q-2) + (1-y+y^(q-1)-y^(q+1))*somma{j=0..h-1}y^(3j)

non si esclude che questi due fattori possano essere scomponibili a
loro volta, ma cio' e' sufficiente a escludere la primalita' di
x^(2n)+x^n+1.

caso 3. q=2 (mod 3), o sia q=3h+2. Posto y=x^(3^k),
x^(2n)+x^n+1=y^(2q)+y^q+1 e' il prodotto di

yy+y+1

e di

y^(2q) + (1-y+y^q-y^(q+2))*somma{j=0..h}y^(3j)

Idem come sopra. Ciao
Massimo Grazzini
2020-12-27 11:18:32 UTC
Permalink
Post by El Filibustero
caso 2. q=1 (mod 3), o sia q=3h+1. Posto y=x^(3^k),
x^(2n)+x^n+1=y^(2q)+y^q+1 e' il prodotto di
yy+y+1 (non di yy-y+1)
Scusa, hai ragione: y^(2q) + y^q + 1 ammette y^2 + y + 1 come divisore sia se q mod 3 = 1, sia se q mod 3 = 2.

Non ammette invece divisori di secondo grado quando q è multiplo di 3.

Sperando di non aver fatto altri errori di conto, aggiungo che il trinomio y^2 - y + 1, divide y^(2q) + y^q + 1
solo in alcuni casi speciali, cioè quando q = 2(3h + 1) o q = 2(3h - 1).

Sull'irriducibilità di x^(2n) + x^n + 1 per n = 3^k, mi riservo di approfondire (del polinomio ciclotomico ho ricordi alquanto nebulosi...)

Grazie e a presto,

Massimo

El Filibustero
2020-12-26 14:37:02 UTC
Permalink
Post by Massimo Grazzini
Con un po' di pazienza si dovrebbe poter provare che
a) x^2 + x + 1 se n mod 3 = 2;
b) x^2 - x + 1 se n mod 3 = 1.
La situazione in generale e' la seguente. Supponiamo n=q*3^k (non
banalmente nullo), con q coprimo con 3.

caso 1. q=1, o sia n e' la k-esima potenza di 3. Allora x^(2n)+^n+1 e'
irriducibile sui razionali, in quanto 3^(k+1)-esimo polinomio
ciclotomico.

caso 2. q=1 (mod 3), o sia q=3h+1. Posto y=x^(3^k),
x^(2n)+x^n+1=y^(2q)+y^q+1 e' il prodotto di

yy+y+1 (non di yy-y+1)

e di

y^(2q-2) + (1-y+y^(q-1)-y^(q+1))*somma{j=0..h-1}y^(3j)

non si esclude che questi due fattori possano essere scomponibili a
loro volta, ma cio' e' sufficiente a escludere la primalita' di
x^(2n)+x^n+1.

caso 3. q=2 (mod 3), o sia q=3h+2. Posto y=x^(3^k),
x^(2n)+x^n+1=y^(2q)+y^q+1 e' il prodotto di

yy+y+1

e di

y^(2q) + (1-y+y^q-y^(q+2))*somma{j=0..h}y^(3j)

Idem come sopra. Ciao
Elio Fabri
2020-12-20 14:12:01 UTC
Permalink
Post by El Filibustero
Esatto. Rilancio: dimostrare che se x^(2n) + x^n + 1 e' primo allora
n e' una potenza di 3. Ciao
L'enunciato è ambiguo: manca il quantificatore su x.

Per n=2 esistono un sacco (infiniti?) valori di x per cui
x^4 + x^2 + 1 è primo, ma anche valori per cui non è primo.
Quindi sospetto che occorra il q. universale, ma non so se è vero.
--
Elio Fabri
Massimo Grazzini
2020-12-25 08:15:53 UTC
Permalink
Post by Elio Fabri
L'enunciato è ambiguo: manca il quantificatore su x.
Sì, direi che bisognerebbe almeno richiedere x intero maggiore di 1.

Quasi di sicuro basta anche "x razionale maggiore di 1".

Per x = 1, si ha ovviamente x^2n + x^n + 1 = 3 (che è primo) per ogni n...
Post by Elio Fabri
Per n=2 esistono un sacco (infiniti?) valori di x per cui x^4 + x^2 + 1 è primo
Di sicuro infiniti. Sia infatti q un numero primo maggiore di 3.

Posto P(q,x) = x^4 + x^2 + 1 - q, si ha P(q, 1) = 3 - q < 0 e P(q, q) = 1 + q(q^3 + q - 1) > 1 + q^4 > 0.

Segue che esiste x_q in ]1; q[ tale che (x_q)^4 + (x_q)^2 + 1 = q.

Massimo
Alessandro Cara
2020-12-22 23:44:30 UTC
Permalink
Post by El Filibustero
Post by effe
2^(10n)+2^(5n)+1= A*B
A=[2^(2n)+2^n+1]
B=[ 2^(8n)-2^(7n)+2^(5n)-2^(4n)+2^(3n)-2^n+1]
Esatto. Rilancio: dimostrare che se x^(2n) + x^n + 1 e' primo allora n
e' una potenza di 3. Ciao
Me ne ero accvorto senza sti "impicci"
--
ac (y-1=x)
Continua a leggere su narkive:
Risultati di ricerca per 'Giochino 71' (newsgroup and mailinglist)
22
risposte
[mezzoOT] giochini sul smartphone
iniziato 2013-07-04 11:40:56 UTC
it.comp.console
10
risposte
[OT] Giochino per annarmene ammale al lavoro..
iniziato 2014-01-21 13:38:23 UTC
it.comp.console
30
risposte
[OT] Giochino Excel stemmi squadre
iniziato 2004-10-27 08:03:05 UTC
it.sport.calcio.milan
11
risposte
[RIESUMAZIONE] Giochino per MSX
iniziato 2014-07-10 08:47:08 UTC
it.comp.console
Risultati di ricerca per 'Giochino 71' (Domande e Risposte)
5
risposte
Perché la direzione è importante quando si utilizza un router elettrico?
iniziato 2015-04-20 22:18:32 UTC
lavorazione del legno
13
risposte
Cosa può fare un professore in caso di esame troppo lungo per il tempo assegnato, dopo che gli studenti lo hanno completato?
iniziato 2015-10-21 20:21:26 UTC
università
8
risposte
Ho sbagliato menzionando le mie abitudini di gioco durante un colloquio di lavoro?
iniziato 2019-11-21 14:31:08 UTC
lavoro
Discussioni interessanti ma non correlate
11
risposte
Esiste la forza centrifuga?
iniziato 2014-04-22 09:43:15 UTC
9
risposte
L'elettricità scorre sulla superficie di un filo o all'interno?
iniziato 2014-04-25 01:30:17 UTC
6
risposte
In che modo la luce si piega intorno alla punta del mio dito?
iniziato 2014-05-03 00:20:47 UTC
10
risposte
Perché non possiamo vedere i gas?
iniziato 2014-05-05 10:53:14 UTC
9
risposte
Perché si dice che senza la meccanica quantistica non avremmo i computer moderni?
iniziato 2014-05-14 04:21:18 UTC
Loading...