I Coprimi

[Alepedra96]

Sono un novizio e non so se questo problema si possa catalogare in teoria dei numeri, ma penso sia il posto più adatto, Dunque: trovare il maggior numero
n<10000 tale che i valori positivi =<n non coprimi con n siano il doppio di quelli coprimi.
Io non ho idee e spero in qualche delucidazione, però se potete non datemi subito la soluzione, preferirei arrivarci da solo anche se con qualche aiuto.

[Triarii]

Ciao e benvenuto
Prima di tutto ti consiglio, per scrivere i testi in maniera più chiara e comprensibile i testi,di usare il latex. Per scrivere magari delle formule con magari delle linee di frazione oppure delle radice, elevamenti a potenza, risulta fondamentale per la chiarezza
Detto questo, non so se ci siano metodi più veloci, però io ho risolto il problema usando la funzione phi, che consente di trovare il numero di numeri coprimi col numero dato. (http://en.wikipedia.org/wiki/Euler%27s_totient_function) Non ti preoccupare delle megaformule in fondo, ti basta la prima!
Detto questo, buon lavoro !
P.s. se ho sbagliato correggetemi, ho fatto il problema un po' di fretta

[Drago96]

Ok, l'ho fatto come te

A me viene

Testo nascosto:

Il massimo numero della forma $2^a3^b$, che non ho voglia di calcolare xD

[Alepedra96]

Grazie mille per l'utile "aiutino"

[Triarii]

Sì Drago pure a me viene come te, e se non ho cannato i conti dovrebbe venire

Testo nascosto:

9216, ossia 2^10 * 3^2

[Alepedra96]

Dovrei aver capito, dunque $ n=3\phi(n) $, quindi $ 3\frac{(p_1-1)(p_2-1)...(p_n-1)}{p_1p_2....p_n}=1 $, ma affinchè il prodotto valga 1,$ p_1=3 $ e diventa $ \frac{2(p_2-1)...(p_n-1)}{p_2....p_n}=1 $, quindi p_2=2 e tutto il resto deve scomparire, dunque il numero deve divisibile solo per 3 e per 2(e le loro potenze).
Il ragionamento è giusto?

[Drago96]

Sì, è esatto
E in questo caso viene 9216

[Alepedra96]

non pensavo di riuscire a farlo, ma visto che qui siete tutti bravissimi posto un altro problema:
quanti sono i numeri interi n, con $ 0<n<285 $ che non hanno alcun multiplo $ m \equiv 1 \pmod{285} $

[Drago96]

In teoria si dovrebbe aprire un nuovo topic per ogni problema, ma questo qua è abbastanza attinente quindi direi che va bene qua...

Per questo problema esiste una cosa carina delle congruenze: l'inverso