Come distruggere un simpatico problemino.

[Troleito br00tal]

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$
!

[Ido Bovski]

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$.

[Troleito br00tal]

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)$?

[jordan]

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$..

[Troleito br00tal]

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}

[kalu]

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$$