Tag Info

5

$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13. A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group). $\mathbb{Z}_{13}$ is a group ...

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

Top 50 recent answers are included