OliForum Matematico

Siano $a;b;c$ interi postivi tali che $(a;c)=1$ e $(a;b)=1$. Mostrare che esiste un $0 < x \le c$ intero positivo tale che, con $y=ax+b$, allora $(y;c)=1$.

Esiste una soluzione davvero raccapricciante (ma anche millemila facili facili, quindi, superpro, non risolvetelo, anche perché potrebbe (ma non lo sarà) essere istruttivo).

Se poi qualcuno avesse tempo da perdere, MIGLIORIAMO IL BOUND DI $x$
!

Ho frainteso io il testo oppure l'ipotesi $(a, b)=1$ non è necessaria?
Comunque un primo miglioramento del bound potrebbe essere $\displaystyle 0<x\le \text{rad}(c)\left(1-\frac{\varphi(c)}{c}\right)+1$.

L'ipotesi effettivamente non è necessaria, ma c'è una soluzione orribile che utilizza quella cosa e (dato che a me piace la bruttezza) ho optato per il tenerla.

Scusa la mia ignoranza, ma cosa è $rad(c)$?

Troleito br00tal ha scritto:Scusa la mia ignoranza, ma cosa è $rad(c)$?

$\text{rad}(c):=\prod_{p \in \mathbb{P}\text{ } :\text{ } p\mid c}{p}$ per ogni intero $c\ge 2$..

Allora si potrebbe anche arrivare a questo. Sia $P$ il più grande primo tale che $P|c$. Allora possiamo anche avere
\begin{equation}
1 \le x \le \frac{2 rad(c)}{P}+1
\end{equation}

Potreste spiegarmi il perchè dei vostri bound, che non ci arrivo?
Comunque una soluzione comoda mi sembra $ \ x_0=\displaystyle\prod_{p\in P\ : \ p \ \mid \ c \ \wedge \ p \ \not\mid \ b}{p} $, che funziona perchè: $$p\mid c \ \wedge \ p\mid b\ \to \ p \not\mid ax_0 \ \to \ p\not\mid y$$ $$p\mid c \ \wedge \ p\not\mid b \ \to \ p\ \mid ax_0 \ \to \ p\not\mid y$$