# Tag Info

## New answers tagged modular-arithmetic

2

Following CodesInChaos request to turn the hint into a full solution, here's a full solution. Let $x$ and $y$ be square roots of $51733469$ modulo $n$. It follows that $$0\equiv x^2-y^2=(x+y)(x-y)\,(\textrm{mod }n).$$ If we choose $x\not\equiv \pm y\, (\textrm{mod }n)$, then $x-y$ and $x+y$ are not divisible by $n$. On the other hand, $n\mid (x+y)(x-y)$, ...

3

a) $2^p \equiv 1 \mod N$ because $2^p = N + 1$. When you reduce $\mod N$ (take the remainder when dividing by $N$), you are left with 1. b) $N - 1 = 2^p - 2$ By Fermat's little theorem, $2^p \equiv 2 \mod p$: $2^p - 2 \equiv 2 - 2 \equiv 0 \mod p$ c) From a) we know that $2^p \equiv 1 \mod N$ From b) we know that $N - 1 \equiv 0\mod p$, therefore ...

1

I might be giving out too much information here (so don't read unless you want spoilers). Anyway, as rings the Chinese Remainder Theorem gives $$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$$ The isomorphism takes $(\mathbb{Z}/n\mathbb{Z})^\times$ to $(\mathbb{Z}/p\mathbb{Z})^\times \times ... 1 Hint: try to prove that$a^{phi(n)/g} \equiv 1 \pmod p$for all$a$satisfying$gcd(a, n) = 1$. Metahint:$phi(n)/g = (p-1) \times (q-1)/g$; is$(q-1)/g\$ an integer?

Top 50 recent answers are included