¿Una condición que implica que dos números sean coprimos?

Question

Consideremos el número natural $n=2^r\cdot s+1$ donde $s$ es impar y supongamos $a\in \mathbb N$ con $1<a<n$ es tal que: $\exists j\in \mathbb N: j<r \wedge a^{2^j\cdot s}\equiv -1 \pmod n$ .

¿Implica esto que $\gcd(a,n)=1$ ?

Answer 1

$a^k \equiv - 1 \mod n$ es imposible a menos que $\gcd(a,n) = 1$ . (Porque $a^k - mn = -1 \implies \gcd(a,n)[\gcd(a,n)^{k-1}\frac{a}{\gcd(a,n)}^{k} - m\frac{n}{\gcd(a,n)}] = -1\implies \gcd(a,n) = 1$ ).

Así que en realidad esto es más sencillo de lo que das a entender.

Answer 2

Un poder de $a$ es congruente con $-1\pmod n,$ que es primo de $n.$ Creo que esto es suficiente para $a$ ser primo de $n,$ como todo divisor común de $a$ y $n$ debe dividir $-1.$
Espero que esto ayude.