TST06- problema 5

[mattilgale]

sia $ A_n $ gli insiemi degli interi a t.c. $ 1\leq a\leq n $ e $ n|(a^n+1) $.

a) per quali n $ A_n\neq\emptyset $?
b) per quali n $ A_n $ ha un numero pari e non nullo di elementi?
c) esiste un n tale che $ |A_n|=130? $

[HiTLeuLeR]

sia $ A_n $ gli insiemi degli interi a t.c. $ 1\leq a\leq n $ e $ n|(a^n+1) $. a) Per quali n $ A_n\neq\emptyset $?

Sia $ n = 2^r q $, dove $ r \in \mathbb{N} $ e $ q \in 2\mathbb{N}+1 $. Innanzitutto, se $ n \mid (a^n + 1) $, necessariamente $ \gcd(a,n) = 1 $. Se dunque r > 0, allora a è dispari, e di conseguenza $ a^n + 1 \equiv 2 \bmod 4 $, per cui a forza r = 0 oppure r = 1. Se r = 0, banalmente $ (n-1) \in A_n $. Se r = 1, allora q non possiede alcun divisore primo p = 3 mod 4. Altrimenti $ a^{n/p} $ sarebbe una soluzione in interi all'equazione $ x^2 \equiv -1 \bmod p $, che tuttavia è irrisolvibile. Se invece q = 1 oppure q è prodotto di soli primi = 1 mod 4, è sempre possibile determinare un dispari $ a\in\overline{1,2q-1} $ tale che $ a^2 \equiv -1 \bmod q $. Basta considerare che: i) se p è un primo = 1 mod 4, l'equazione $ x^2 \equiv -1 \bmod p $ è risolubile in interi; ii) se p è primo ed $ n \in \mathbb{N}^+ $, l'equazione $ x^2 \equiv -1 \bmod p^{n+1} $ è risolubile in Z se lo è l'equazione $ x^2 \equiv -1 \bmod p^n $; ii) $ (a^2 + 1) \mid (a^{2q}+1) $, per ogni $ a\in\mathbb{Z} $. Da qui, $ A_n \ne \emptyset $ sse n = 1 (basta porre in tal caso a = 1) oppure n è prodotto di soli fattori primi = 1 mod 4 oppure n è due volte il prodotto di soli fattori primi = 1 mod 4.

[HiTLeuLeR]

b) per quali n $ A_n $ ha un numero pari e non nullo di elementi?

Ovviamente $ |A_n| \le \phi(n) $, per cui dev'essere n > 2. Se poi p è primo ed $ a\in\mathbb{Z} $, allora $ a^{2p} \equiv 1 \bmod p $ sse $ a^2 \equiv 1 \bmod p $ (piccolo th. di Fermat), per cui $ a=kp \pm 1 $, con $ k \in \mathbb{Z} $. Di conseguenza, se $ n\in\mathbb{N}^+ $ e $ a^{2p^n} \equiv 1 \bmod p^n $, allora $ \displaystyle 1 \equiv (kp \pm 1)^{2p^n} \equiv \sum_{i=0}^{2p^n} (-1)^i \binom{2p^n}{i} (kp)^i \bmod p^n $, il che è vero per ogni $ k\in\mathbb{Z} $, siccome $ \displaystyle\binom{2p^n}{i} k^i p^i \equiv 0 \bmod p^n $, qualunque sia $ i = 1, 2, \ldots, 2p^n $. Ne risulta che, se $ 2\prod_{i=1}^r p_i^{\alpha_i} $ è la fattorizzazione canonica di n, dove $ p_i $ è un primo = 1 mod 4 ed $ \alpha_i $ un intero positivo, ogni soluzione in numeri interi all’equazione $ a^n + 1 \equiv 0 \bmod n $ è del tipo $ a_k = kp_1 p_2 \ldots p_r \pm 1 $, con $ k\in\mathbb{Z} $. Con riferimento al punto a) del quesito, distinguiamo a questo punto due possibili casi:

i) n = 2q, dove $ q = \prod_{i=1}^r p_i^{\alpha_i} $ è prodotto di soli primi $ p_i \equiv 1 \bmod 4 $ e $ \alpha_i \in \mathbb{N}^+ $. Osserviamo che $ a \in A_n $ sse $ (n-a) \in A_n $, e che a = n-a sse a = q. Senonché $ q \nmid (q^{2q}+1) $, per cui $ q \not\in A_n $, e di conseguenza $ |A_n| $ è pari. Più quantitativamente, ogni soluzione in interi all’equazione $ a^{n} + 1 \equiv 0 \bmod n $ è del tipo $ a_k = 2kP \pm 1 $, con $ k\in\mathbb{Z} $ e $ P = p_1 p_2 \ldots p_r $, e viceversa (btw, il fattore 2 fa la sua comparsa per via del fatto che a necessita essere dispari). In particolare, $ a_k \in A_n $ per $ 2n/P $ valori distinti di k, cosicché $ |A_n| = 2n/P $.

ii) $ n = \prod_{i=1}^r p_i^{\alpha_i} $ è prodotto di soli primi $ p_i \equiv 1 \bmod 4 $ e $ \alpha_i \in \mathbb{N}^+ $. Le soluzioni in interi all’equazione $ a^n + 1\equiv 0 \bmod n $ sono in tal caso tutte e sole della forma $ a_k = kP $ – 1, con $ k\in\mathbb{Z} $ e $ P = p_1 p_2 \ldots p_r $. In particolare, $ a_k \in A_n $ per $ n/P $ valori distinti di k, e perciò $ |A_n| = n/P $ è dispari.

Conclusione: $ A_n $ ha un numero pari e non nullo di elementi sse n = 2q, dove q è un prodotto (non vuoto) di primi = 1 mod 4.

[HiTLeuLeR]

c) esiste un n tale che $ |A_n|=130? $

Sì. Con riferimento al caso i) della soluzione al quesito b), basta assumere $ n = 2 \cdot 5^2 \cdot 13^2 $.

[Boll]

Ahiahiahi, euler, il problema ha fregato (soprattutto nelle conclusioni più che nel metodo) fior di olimpionici, ma da te non me l'aspettavo...

Ti rimando a Soluzioni del TST pagina 31-32

[HiTLeuLeR]

Ooops! Vabbè, la lascio così, in memoria di non_so_dir_esattamente_che.

To do: esercitarsi nell'uso del teorema cinese dei resti.