Divisori, Eulero, Fattoriali

[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!$

[mr96]

Sono solo

Testo nascosto:

32,45,18,75,50,20,12

? Se si appena ho un pc posto la dimostrazione

[Claudio.]

Sono solo

Testo nascosto:

32,45,18,75,50,20,12

? Se si appena ho un pc posto la dimostrazione

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.

[mr96]

Sono solo

Testo nascosto:

32,45,18,75,50,20,12

? Se si appena ho un pc posto la dimostrazione

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ò

[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.

[Claudio.]

Per qualche ragione li ho calcolati tutti, dovrebbero essere:

Testo nascosto:

[math]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.

[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?

[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à.

[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]

[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

[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