Pagina 1 di 1

Divisori, Eulero, Fattoriali

Inviato: 10 mag 2016, 14:52
da Talete
Determinare tutti i numeri naturali $n$ che soddisfano contemporaneamente le seguenti proprietà:

(i) il numero di divisori positivi di $n$ è uguale a $6$;

(ii) $\phi(n)$ è divisore di $6!$

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 15:49
da mr96
Sono solo
Testo nascosto:
32,45,18,75,50,20,12
? Se si appena ho un pc posto la dimostrazione :D

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 18:31
da Claudio.
mr96 ha scritto:Sono solo
Testo nascosto:
32,45,18,75,50,20,12
? Se si appena ho un pc posto la dimostrazione :D
Te ne sei persi un po'...
Testo nascosto:
52, 76, 124, 148, 164, 244, 292, 724...
E ce ne sono altri, a parte farli a mano non ho trovato però un buon metodo per calcolarli.

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 18:46
da mr96
Claudio. ha scritto:
mr96 ha scritto:Sono solo
Testo nascosto:
32,45,18,75,50,20,12
? Se si appena ho un pc posto la dimostrazione :D
Te ne sei perso un po'...
Testo nascosto:
52, 76, 124, 148, 164, 244, 292, 724...
E ce ne sono altri, a parte farli a mano non ho trovato però un buon metodo per calcolarli.
Ok, si, ho fatto un po' di casino... Ci riproverò :lol:

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 19:13
da Claudio.
Per qualche ragione li ho calcolati tutti, dovrebbero essere:
Testo nascosto:
12, 18, 20, 24, 32, 44, 50, 52, 63, 75, 76, 99, 117, 124, 148, 164, 175, 244, 279, 292, 325, 369, 724, 925
Ma senza una calcolatrice ed una tavola dei numeri primi il mio metodo sicuramente non è fattibile.

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 19:42
da Claudio.
Claudio. ha scritto:Per qualche ragione li ho calcolati tutti, dovrebbero essere:
Testo nascosto:
[math]
Ma senza una calcolatrice ed una tavola dei numeri primi il mio metodo sicuramente non è fattibile.

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 21:27
da Talete
Non sono tutti, e non tutti quelli che hai scritto sono giusti.

Esempio: manca il numero $28$, che ha come divisori $1$, $2$, $4$, $7$, $14$ e $28$ (quindi ne ha $6$) e $\phi(28)=6$, che è un palese divisore di $6!$
Esempio: hai scritto il numero $24$, ma ha come divisori $1$, $2$, $4$, $8$, $3$, $6$, $12$, $24$ (che sono $8$).

Btw, io l'ho risolto senza calcolatrici né tavole: basta sapere un paio di primi relativamente alti, tipo $61$. Tu come hai fatto? ;)

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 22:27
da Claudio.
Il 24 è un typo per 28. Potrebbero esserci altri errori. Non ho ricontrollato comunque.
I numeri con 6 divisori sono di forma $p^5$ o $p_1p_2^2$
Nel primo caso $\phi(p^5)=p^5-p^4=p^4(p-1)$ e da $p^4(p-1)|720 \to p\le3$ da cui otteniamo solo $2^5$.
Nel secondo caso $\phi(p_1p_2^2)=p_1p_2^2-p_1^2-p_1p_2+p_2=p_2(p_2-1)(p_1-1)\to p_2\in \{2,3,5\}$ perciò bisogna cercare i primi p per cui $p-1|360, 120, 36$ da cui quella roba là.

Re: Divisori, Eulero, Fattoriali

Inviato: 17 mag 2016, 23:39
da fph
Facendolo fare brutalmente a Sage:

Codice: Seleziona tutto

[n for n in srange(10000) if euler_phi(n).divides(factorial(6)) and len(divisors(n))==6]
[12, 18, 20, 28, 32, 44, 45, 50, 52, 63, 75, 76, 99, 117, 124, 148, 164, 175, 244, 279, 292, 325, 369, 475, 549, 724, 925]

Re: Divisori, Eulero, Fattoriali

Inviato: 18 mag 2016, 02:25
da Talete
Sì ok, il metodo risolutivo è il medesimo.
Testo nascosto:
$n$ è o della forma $p^5$ o della forma $p^2q$ (altrimenti non ha $6$ divisori)

Adesso, $\phi(n)=p^4(p-1)$ nel primo caso, che dovendo dividere $2^4\cdot3\cdot5$ porta a $n=32$.

Nel secondo caso, $\phi(n)=p(p-1)(q-1)$, ora chiaramente $p$ è tra $2$, $3$ e $5$.

$p=2$ porta a: $q-1$ divide $2^3\cdot3^2\cdot5$, e da qui $q-1$ può essere $1$, $2$, $4$, $8$, $3$, $6$, $12$, $24$, $5$, $10$, $20$, $40$, $9$, $18$, $36$, $72$, $15$, $30$, $60$, $120$, $45$, $90$, $180$, $360$. Si ricavano i $q$ primi che vanno bene ($3$, $5$, $7$, $13$, $11$, $41$, $19$, $37$, $73$, $31$, $61$, $181$) e quindi gli $n$ che vanno bene ($12$, $20$, $28$, $52$, $44$, $164$, $76$, $148$, $292$, $124$, $244$, $724$)

$p=3$ porta a: $q-1$ divide $2^3\cdot3\cdot5$, e da qui $q-1$ può essere $1$, $2$, $4$, $8$, $3$, $6$, $12$, $24$, $5$, $10$, $20$, $40$, $15$, $30$, $60$, $120$. Quindi $q$ può essere $2$, $5$, $7$, $13$, $11$, $41$, $31$, $61$ e $n$ quindi $18$, $45$, $63$, $117$, $99$, $369$, $279$, $549$.

$p=5$ porta a: $q-1$ divide $2^2\cdot3^2$, e da qui $q-1$ può essere $1$, $2$, $4$, $3$, $9$, $6$, $12$, $18$, $36$, quindi $q$ è tra $2$, $3$, $7$, $13$, $19$, $37$ e dunque $n$ è $50$, $75$, $175$, $325$, $475$, $925$.

In totale $n$ può essere:
$12$, $18$, $20$, $28$, $32$, $44$, $45$, $50$, $52$, $63$, $75$, $76$, $99$, $117$, $124$, $148$, $164$, $175$, $244$, $279$, $292$, $325$, $369$, $475$, $549$, $724$, $925$
Tutto considerato, te ne sei persi un po' ma la maggior parte li hai trovati (e il ragionamento era giusto). Comunque auguriamoci che un problema del genere non ci capiti MAI in gara ;)

Re: Divisori, Eulero, Fattoriali

Inviato: 18 mag 2016, 09:17
da mr96
Stessa cosa che ho fatto io, peccato che (stupidamente) mi sia peso il fatto che q può essere qualsiasi cosa... Mi ero convinto di dover avere q-1 = 2,3,5 :?