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} $
- 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 ...
- 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 ...
- 491k
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.
- 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$...
- 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)...
- 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,...
- 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|+...
- 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-...
- 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(...
- 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 ...
- 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$...
- 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^...
- 269k
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\...
- 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 ...
- 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}$) ...
- 2,647
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 ...
- 872
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 $...
- 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 ...
- 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 ...
- 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$ ...
- 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+...
- 11.5k
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 ...
- 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 $...
- 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$.
- 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...
- 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$ ...
- 209k
Only top scored, non community-wiki answers of a minimum length are eligible