OliForum Matematico

Problema: determinare ogni $ n\in\mathbb{N} $ tale che gli interi positivi $ \leq n $ e coprimi con $ n $, presi in un qualche ordine, stiano fra loro in progressione aritmetica (la fonte è ancora il nostro Azarus).

Cosa intendi con "presi in qualche ordine"? L'ordine di una progressione aritmetica non è sempre crescente?

O sempre decrescente. Non che cambi molto in questo caso...

Bè, proviamoci. Non sono un granché in teoria dei numeri, quindi perdonatemi qualche passaggio di troppo o anche qualche cavolata.

Cerco una prog. aritmentica con ragione r che parte sicuramente da 1 (perché (1,n)=1 per ogni intero positivo) e finisce in n-1 ((n-1,n)=1).
Se n è dispari, allora (2,n)=1, quindi r=1. Questo ci dice che (k,n)=1 per ogni k minore di n, ossia che n è primo; quindi tutti i primi dispari vanno bene.
Se n è pari ma non divisibile per 3, r=2. Dunque n dev'essere coprimo con tutti i dispari <n; quindi n deve contenere solo il fattore 2, ed è facile vedere che tutte le potenze di 2 vanno bene.
Resta il caso di n multiplo di 6.
Se $ r\equiv 0 \pmod3 $ allora $ n-1\equiv 1 \pmod3 $, assurdo perché avevamo supposto n multiplo di 3
Se $ r\equiv 1 \pmod 3 $ abbiamo $ (1+2r,n)\geq 3 $. Quindi necessariamente 1+2r>n, ossia $ \phi(n)\leq 2 $ che ci dà n=6 come soluzione.
Se $ r\equiv 2 \pmod 3 $ allora (1+r,n) sarebbe almeno 3. Perciò $ \phi(n)=1 $ che non ha soluzioni.

Ricapitolando, le soluzioni sono tutti i primi dispari, le potenze di 2, ed il caso particolare n=6. In più ci sarebbe n=1, ma non so se ha senso parlare di progressione aritmetica di un solo elemento.

what ha scritto:Cosa intendi con "presi in qualche ordine"?

Fissato $ n\in\mathbb{N}_0 $, diciamo $ t_1, t_2, \ldots, t_p $ gli interi positivi $ \leq n $ e coprimi con $ n $. Ora, è chiaro che l'ordinamento indiciale degli elementi della famiglia $ \{t_i\}_{i=1}^p $ non deve rispettare a forza l'ordinamento naturale degli interi. Dunque il fatto che $ t_1, t_2, \ldots, t_p $ stiano fra loro in progressione aritmetica potrebbe anche dipendere, in linea di principio, dall'indicizzazione scelta...

what ha scritto:L'ordine di una progressione aritmetica non è sempre crescente?

...L'osservazione tua e l'altra di Sisifo ti dispensano tuttavia dal doverne tener conto.

what ha scritto:[...] Se $ r\equiv 1 \pmod 3 $ abbiamo $ (1+2r,n)\geq 3 $. Quindi necessariamente $ 1+2r>n $ [...]

Perché dici che necessariamente $ 1+2r > n $?

HiTLeuLeR ha scritto:Perché dici che necessariamente $ 1+2r > n $?

Bè, 1+2r fa parte della progressione aritmetica (infinita) che parte da 1 e ha ragione r. Se fosse minore di n, allora (1+2r,n)=1, assurdo.
In effetti avrei dovuto scrivere $ 1+2r\geq n $

Ok! Comunque il segno di maggiore stretto ci sta benissimo, siccome stai ammettendo che $ n $ sia multiplo di $ 6 $ (quindi pari), dove invece $ 2r+1 $...