23 votes

Proof that square of an $\sqrt{2 - 4q}$ is not an integer

Hint : If $n$ is some integer, then $n=0 \mod{4} \implies n^2=0 \mod{4} $ $n=1 \mod{4} \implies n^2=1 \mod{4} $ $n=2 \mod{4} \implies n^2=0 \mod{4} $ $n=3 \mod{4} \implies n^2=1 \mod{4} $
user avatar
  • 2,300
18 votes
Accepted

Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

The original question was to prove that $c\mid a^2+b^2$ implies $c\mid a$ and $c\mid b$, which as many answers show isn't true. But this is true if you take the assumption that there isn't a square ...
user avatar
  • 14.2k
18 votes

$xy$ is a quadratic residue mod $p$ iff $x$ is a quadratic residue mod $p$, where $y$ be a (nonzero) quadratic residue mod $p$

Suppose that $xy$ is a QR of $p$. Then $xy\equiv z^2\pmod{p}$ for some $z$. Since $y$ is a QR of $p$, we have $y\equiv w^2\pmod{p}$ for some $w$. Thus $xw^2\equiv z^2\pmod{p}$. Multiply both sides ...
user avatar
17 votes

Proof that square of an $\sqrt{2 - 4q}$ is not an integer

Apart from @Vincent's answer, here's another way of looking at it $$x=\sqrt{2-4q}$$ Clearly, $2-4q$ is divisible by $2$ but not by $4$ for any integer $q$. Thus, it cannot be a perfect square.
user avatar
  • 11.1k
15 votes
Accepted

Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?

"I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute." Ok, so perhaps you are looking at Fermat's Little Theorem, where $n$ is prime, and $a$...
user avatar
  • 2,343
14 votes

When is $2$ a quadratic residue mod $p$?

Let $s = \frac{p-1}{2}$, and consider the $s$ equations $$\begin{align} 1&= (-1)(-1) \\ 2&=2(-1)^2 \\ 3&= (-3)(-1)^3 \\ 4&= 4 (-1)^4 \\ & \quad\quad \ldots\\ s&= (\pm s)(-1)...
user avatar
  • 86.3k
13 votes

When is $-3$ a quadratic residue mod $p$?

Here’s an argument that doesn’t depend on Quadratic Reciprocity. First, for $-3$ to be a quadratic residue modulo $p$, that’s the same as having a $\sqrt{-3}$ in the field $\Bbb F_p$ with $p$ elements,...
user avatar
  • 59.6k
12 votes

Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.

Let: $$A=\{x^2|x\in \Bbb Z_p\},\ \ \ \ \ \ \ B=\{-(1+y^2)|y\in \Bbb Z_p\}$$ it is known that $$|A|=|B|=\frac{p+1}{2}$$ (maybe you can try to prove this ), if $A\cap B=\varnothing$ then $|A\cup B|=|A|+...
user avatar
  • 13.4k
12 votes

Proof that square of an $\sqrt{2 - 4q}$ is not an integer

Let $x \in \Bbb Z$ be a solution. Of course $x$ must be even, since an odd $x$ would make $2-x^2$ odd too. Now let $x=2y$, then $2-x^2=2-4y^2=2(1-2y^2)$. But $1-2y^2$ is odd, so $4$ can't divide $2-...
user avatar
  • 1,909
11 votes
Accepted

Proving or disproving $12\mid x$ given $x^2+2\mid y^2-2$

If $3\nmid x$ then $$ x^2\equiv 1\pmod 3\implies x^2+2\equiv 0\pmod 3$$ so $$ 3\mid y^2-2$$ which means $2$ is a square modulo 3. But this does not hold so $3\mid x$. If $x$ is odd, then $x^2+2 = 4k(...
user avatar
  • 86.6k
10 votes
Accepted

Inifinitely many primes $p\equiv -1 \mod12$

Suppose there are only finitely many primes of this form, say $\{p_1,\dots,p_n\}$. Let $P = p_1\dots p_n$ denote their product. Consider now the following expression: $$Q = 12P^2-1$$ Then we observe ...
user avatar
  • 3,626
10 votes
Accepted

2016 Spain Math Olympiad final stage, problem 2

For $p=2$, or any prime where $3=25$, the conditions are identical. For odd primes, $x^2 - x = a$ is solvable if and only if $4a+1$ is a perfect square. The statement is now that $-11$ and $-99$...
user avatar
  • 34.4k
9 votes
Accepted

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

For $p=2,$ $$(x^2-2)(x^2-3)(x^2-6)\equiv x^2(x^2-1)x^2\pmod2$$ But $x^2(x^2-1)x^2$ is divisible by $x(x-1)$ which being a product of two consecutive integers is always divisible by $2$ $$(x^2-2)(x^...
user avatar
9 votes

Prove that $\sum_{X=0}^{p-1} \left(\frac{X^{2}+A}{p}\right)=-1$

Fix an odd prime natural number $p$. Let $$S_p(A):=\sum_{x\in\mathbb{F}_p}\,\left(\frac{x^2+A}{p}\right)$$ for all $A\in\mathbb{F}_p^\times$, where $\mathbb{F}_p^\times$ is the group $\mathbb{F}_p\...
user avatar
  • 48.5k
9 votes

If for the first $\|n\|$ primes $p_i, \left(\frac{p_i}n\right)=+1$, then $n$ is a square

This is not known. However, it may be provably false under the Generalized Riemann Hypothesis (GRH), depending on a constant calculated in a paper of Montgomery. Least Quadratic Non-Residue You are ...
user avatar
  • 69.9k
8 votes
Accepted

When does -1 have a squareroot in a finite field? (-1 as a quadratic residue)

Since the unit group of a finite field $\mathbb{F}$ is always cylic of order $|\mathbb{F}|-1=:n$ and $-1$ is the unique element of order $2$ in $\mathbb{F}^ \times$ (if $1 \neq -1$ in $\mathbb{F}$) ...
user avatar
8 votes
Accepted

Find smallest prime $p$ such that all primes $q < 40$ are quadratic non-residues $\pmod p$

This is just a tiny bit more involved than Wolfram Alpha can handle: Select[Prime[Range[100]], Union[JacobiSymbol[Prime[Range[12]], #]] == {-1} &] The answer ...
user avatar
8 votes

If $p$ is prime, then $x^2 +5y^2 = p \iff p\equiv 1,9 $ mod $(20)$.

An alternative solution: the class number of $K=\mathbb{Q}(\sqrt{-5})$ is $2$, its Hilbert class field is $L=\mathbb{Q}(\sqrt{-5},\sqrt{-1})$. A prime $p\neq 2,5$ can be written as $p=x^2+5y^2$, iff $...
user avatar
  • 17.8k
7 votes
Accepted

Do there exist Artificial Squares?

Suppose that $E = p^{2k+1} n$ where $(n,p) = 1$. Take $w = p^{2k+2}$. If $E$ is a quadratic residue modulo $p^{2k+2}$ then there exists $m$ such that $$ p^{2k+2} \mid p^{2k+1} n - m^2. $$ In ...
user avatar
  • 55.6k
7 votes

Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?

By Fermat's little theorem, $a^{24} = (a^{12})^2 \equiv 1^2 = 1 \pmod{13}$ (assuming $13\nmid a$, which is the case here).Thus you're really trying to solve $1\equiv6a+2\pmod{13}$, which is much ...
user avatar
  • 64.3k
7 votes
Accepted

Proof that square of an $\sqrt{2 - 4q}$ is not an integer

This answer builds completely on GoodDeed's excellent answer, but I think going into further detail is useful. Consider that $$x=\sqrt{2-4q} = \sqrt{2 (1 - 2q)} = \sqrt 2 \sqrt{1 - 2q}$$ $1 - 2 q$ ...
user avatar
  • 261
7 votes

$-3$ is a quadratic residue iff $p \equiv 1 \pmod 3$

Your idea is right! But note that $$\left (\frac{-3}{p}\right)=1\iff p\equiv_61$$ is a stronger and better condition than $p\equiv_3 1$, why? Look at all the numbers $n\equiv_3 1$ (that is, $n=1+...
user avatar
7 votes
Accepted

Visualizing quadratic residues and their structure

This is not a complete answer to all of your questions. This is to show you some things you need to investigate. The first question is answered. The second question has an example. I do not know ...
user avatar
  • 17.8k
7 votes
Accepted

Show that a following equation has no solution in integers: $x^3-x+9=5y^2$

Aqua, here it is. As you've obtained, $x\equiv 2\pmod{5}$. Now, $x(x-1)(x+1)=5y^2-9$. Note that, $x+1\equiv 3\pmod{5}$, and is odd. I now claim that, there is a prime $p\mid x(x-1)(x+1)$ such that $...
user avatar
  • 3,346
6 votes

Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

This is not true. Take, for example, $a=3$, $b=4$ and $c=5$.
user avatar
  • 847
6 votes
Accepted

For a prime $p\ge 17$ is $\dfrac{p^2-1}{24}$ ever a prime?

When $p-1>24$, then $24$ can't cancel any of the factors $p-1$ and $p+1$ properly, so the number $\frac{p^2-1}{24}$ is always composite for $p-1>24$, other cases can be calculate manually...
user avatar
  • 5,198
6 votes
Accepted

If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.

The key point is that if $3$ does not divide $x$, then $x^2$ leaves remainder $1$, because $x$ is of the form $3k\pm1$. Therefore: If $3$ divides $a$ but not $b$ (or vice-versa), then $a^2+b^2$ ...
user avatar
  • 209k

Only top scored, non community-wiki answers of a minimum length are eligible