Sottoinsiemi coprimi di {1,2,...,n}
Inviato: 06 nov 2009, 05:17
Mostrare che $ f(n):=|\{A \subset \{1,2\ldots,n\} \text{ tale che } \text{gcd}(x \in A) = 1\}| $ non è un quadrato perfetto per ogni intero n>1.
Suppongo che non siano ammessi $ \displaystyle~A $ vuoti.. $ \displaystyle~f(1)=1 $. La tesi segue dal fatto che $ \displaystyle~f(n)\equiv -1\pmod 3~\forall n>1 $.
Per dimostrare ciò notiamo anzitutto che $ \displaystyle~f(n)=2^n-1-\sum_{i=2}^n f(\left\lfloor\frac{n}{i}\right\rfloor) $. Perché? $ \displaystyle~2^n-1 $ è il numero di possibili sottoinsiemi non vuoti di $ \displaystyle~\{1,2,...,n\} $ senza la condizione $ \displaystyle~\text{gcd}(x \in A) = 1 $: a questa quantità vanno sottratti i sottoinsiemi con gcd = 2 (che sono tutti quelli di $ \displaystyle~f(\left\lfloor\frac{n}{2}\right\rfloor) $ con gli elementi moltiplicati per 2), quelli con gcd = 3 etc.
Ora possiamo dimostrare la tesi per induzione:
Passo base: $ \displaystyle~f(2)=2\equiv -1\pmod 3 $
Passo induttivo: $ \displaystyle~f(n)=2^n-1-\sum_{i=2}^n f(\left\lfloor\frac{n}{i}\right\rfloor)\equiv -1\pmod 3 $ sse $ \displaystyle~(-1)^n\equiv\sum_{i=2}^n f(\left\lfloor\frac{n}{i}\right\rfloor)\pmod 3 $. I termini della sommatoria con $ \displaystyle~i\le\frac{n}{2} $ danno $ \displaystyle~\left\lfloor\frac{n}{i}\right\rfloor\ge 2 $, dunque per ipotesi induttiva i primi $ \displaystyle~\left\lfloor\frac{n}{2}\right\rfloor-1 $ termini sono $ \displaystyle~\equiv -1\pmod 3 $. Gli altri termini sono $ \displaystyle~\left\lfloor\frac{n+1}{2}\right\rfloor $ uni. Quindi $ \displaystyle~(-1)^n\equiv\sum_{i=2}^n f(\left\lfloor\frac{n}{i}\right\rfloor)\pmod 3 $ sse $ \displaystyle~(-1)^n\equiv\left\lfloor\frac{n+1}{2}\right\rfloor-\left\lfloor\frac{n}{2}\right\rfloor+1\pmod 3 $. Se n pari funziona, se dispari anche dunque abbiamo che $ \displaystyle~f(n)\equiv-1\pmod 3~\forall i> 1 $.
