Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc.. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

1
vote
2answers
34 views

Let $a$ be a quadratic residue modulo $p$. Prove that the number $b\equiv a^\frac{p+1}{4} \mod p$ has the property that $b^2\equiv a \mod p$.

Let $p$ be a prime satisfying $p\equiv 3 \mod 4$. Let $a$ be a quadratic residue modulo $p$. Prove that the number $$b\equiv a^\frac{p+1}{4} \mod p$$ has the property that $b^2\equiv a \mod p$. (Hint: ...
0
votes
2answers
33 views

Order of Elements in $Z_{12}$

So I know all the orders of the elements in $(Z_{12},+)$ $|[0]| = 1$ $|[1]| = 12$ $|[2]| = 6$ $|[3]| = 4$ $|[4]| = 3$ $|[5]| = 12$ $|[6]| = 2$ $|[7]| = 12$ $|[8]| = 3$ $|[9]| = 4$ $|[10]| = ...
-4
votes
0answers
35 views

Number Theory questions [duplicate]

Let $a$ be an integer and $n$ a positive integer. Prove or provide a counter example to each of the following statements. (a) If $a$ ≡ ± 1(mod p) for all primes $p$ dividing $n$, then $a^2$ ≡ 1(mod ...
3
votes
4answers
83 views

Prove that $5 \nmid (a+1)^3 - a^3$

Prove that difference between two consecutive cubes cannot be divided by $5$. Here's what I've done, but I'm not sure about one step: Let two cubes be $(a+1)^3$, and $a^3$. $$(a+1)^3 - a^3 = ...
0
votes
2answers
55 views

Evaluating arithmetic sum using prime factorization [duplicate]

Please help! I have no idea how to start this problem / what to do to evaluate this. For m>0 , let f(m) = $\sum_{r=1}^{m} \frac{m}{gcd(m,r)}$ . Evaluate f(m) in terms of the prime factorization of m. ...
3
votes
1answer
55 views

Proof of Fermat's last theorem for $n=5$ using primitive roots of unity?

I've been reading "An introduction to the theory of numbers" by Hardy and Wright and they gave a nice proof of Fermat's last theorem for $n=3$ by proving that there are no solutions to ...
1
vote
1answer
35 views

How many infinite subsets of the Naturals have natural density (asymptotic density) zero?

Are there countably or uncountably many? I know that the set of all primes has density zero. Is there an obvious way of using that result to construct an uncountable family of such sets?
0
votes
2answers
20 views

Quadratic reciprocity: $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$

Prove $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$, where $p$ is an odd prime, and the LHS is the legendre symbol. I've got $-1 = x^2 \pmod p \implies (-1)^{\frac{p-1}{2}} = x^{p-1} = 1 = ...
2
votes
2answers
39 views

If $K:=\mathbb Q\left(\sqrt{-3}\right)$ and $R$ is the ring of integers of $K$, then $R^{\times}=\mathbb Z\big/6\mathbb Z$

How to show that if $K:=\mathbb Q\left(\sqrt{-3}\right)$ and $R$ is the ring of integers of $K$, then the group of units $R^{\times}=\mathbb Z\big/6\mathbb Z$ Now since $-3\equiv1\mod 4$ the ring ...
1
vote
2answers
32 views

Reference request for a special kind of numbers.

Let $q$ be an element of a field $k$ (possibly $\mathbb{C}$), different from $-1$ and $1$. We have $$[n]=\frac{q^n-q^{-n}}{q-q^{-1}}=q^{n-1}+q^{n-2}+\dots+q^{-n+1}$$ Where $n$ is a natural number. ...
2
votes
0answers
28 views

Generalization of Dirichlet convolution

The Wikipedia page on the Mobius inversion formula gives the following formula in passing: if $$G(x)=\sum_{k=1}^x \alpha(x)F(x/k)$$ for some arithmetic function $\alpha(n)$ possessing a Dirichlet ...
3
votes
2answers
66 views

Reference to complete proof that integral closure of $\mathbb{Z}$ in $\mathbb{Q}(i)$ is $\mathbb{Z}[i]$?

Where can I find a complete proof to the fact that the integral closure of $\mathbb{Z}$ in $\mathbb{Q}(i)$ is $\mathbb{Z}[i]$ (the Gaussian integers are the integral closure of $\mathbb{Z}$ in the ...
0
votes
0answers
22 views

How is pollard rho different from normal factorization?

As far as I understand, pollard rho factorization generates random sequence of numbers, say x1, x2, x3 ... and then checks if x(i) - x(i-1) divides the number. If it does then it is a factor. How is ...
1
vote
2answers
14 views

Why is $\sum_{d\mid p^r}\phi(d)=\sum_{h=0}^r\phi(p^h)$

$\sum_{d\mid p^r}\phi(d)=\sum_{h=0}^r\phi(p^h)$ I read this relation in a proof, but can't work out why it is the case. Thanks in advance for the help.
1
vote
1answer
49 views

Is $p\in\big\{x,…,2x\big\}$ lower-bounding $p\in\big\{x^2,…,(x+1)^2\big\}$?

Is it overreaching or erroneous to consider that possibility? (Alas, I'm not a mathematician, and don't have rigorous language to talk about this.) What I want to say is: Given any even span of ...
4
votes
3answers
93 views

Is the algebraic closure of $\mathbb Q$ in the field $\mathbb Q_5$ a number field?

Is the algebraic closure of $\mathbb Q$ in the field $\mathbb Q_5$ of $5$-adic numbers a number field, if yes what is the degree ? To be honest I don't understand the question, what does it mean ...
3
votes
2answers
66 views

Faster Sage Code for Diophantine Equation? [closed]

I'm having trouble with the computation time. Does anyone have any ideas for faster code? ...
7
votes
1answer
80 views

Proving that $n$ and $m$ divides $1^{n}+2^{n}+3^{n}+\cdots+m^{n}$

For which positive integers $m, n$ is true that the number $$1^{n}+2^{n}+3^{n}+\cdots+m^{n}$$ is divisible by $n$ and $m$?
4
votes
1answer
37 views

Are Mersenne numbers $M_p$ deficient?

A positive integer $n$ is called deficient if $\sigma(n)<2n$, i.e., the sum of divisors is less than $2n$. What is known about Mersenne numbers $n=2^p-1$ with $p$ prime in this respect ? Is there a ...
0
votes
1answer
20 views

PIE Problem with divisors

Find the number of positive integers that are divisors of at least one of $10^{10},15^7,18^{11}$. Let $n(A)$ be the number of positive integers that divide $10^{10}$ let $n(B)$ be the number of ...
1
vote
5answers
33 views

When $p=2$ or $p$ prime, with $p=1\pmod{4}$, $x^2\equiv -1\pmod{p}$ is soluble - trouble understanding proof

Theorem: When $p=2$ or $p$ prime, with $p=1\pmod{4}$, $x^2\equiv -1\pmod{p}$ is soluble Proof: When $p=2$, the statement is clear. Assume $p\equiv 1\pmod{4}$, let $r=\frac{p-1}{2}$ and $x=r!$ Then ...
7
votes
0answers
49 views

A comment in the Disquisitiones Arithmeticae

Gauss proves that if $t\equiv\pm 3\mod 8$, then $2$ is a non-(quadratic)-residue modulo $t$ as follows: Assume $t\equiv\pm 3\mod 8$ is the smallest counter-example, and say $a^2\equiv 2\mod t$, ...
0
votes
2answers
33 views

Polynomial Congruence problem

We are asked to find the solutions to the following congruence $$ x^3 + 8x^2 - x - 1 \equiv 0 \ (\text{mod } 11). $$ I know that the solution can be computed using Hensel's Lemma or by simply using ...
1
vote
1answer
14 views

What does it mean by “level sets of $\bar{G}$, a collection of forms, partition those of $\bar{F}$, another collection of forms”

I was reading an article and I was wondering if someone could explain me what a certain phrase meant. Let $\bar{F}$ be a collection of integral forms of degree less than or equal to $d$. And suppose ...
4
votes
1answer
99 views

Why is it called the Fundamental Theorem of Arithmetic?

The Fundamental Theorem of Arithmetic is easy enough to understand, saying that every integer greater than 1 is either prime or is the product of a unique combination of prime numbers. What I don't ...
4
votes
1answer
63 views

Maybe is right $\frac{n^2 + 1}{4k + 3} \notin \mathbb{Z}, n, k \in \mathbb{N}^{+}$

Prove or disprove $$\dfrac{n^2 + 1}{4k + 3} \notin \mathbb{Z}, n, k \in \mathbb{N}^{+}$$ I know if $n^2 + 1$ is prime if and only if $n^2 + 1 \equiv 1 \pmod 4$.
1
vote
2answers
27 views

How can a subgroup have multiple cosets?

I am currently reading An Introduction To The Theory Of Groups, by Joseph Rotman, and in a section describing cosets, there is an exercise question as follows; Let $H$ be and subgroup of $G$ having ...
1
vote
1answer
46 views

How to count each numeral of occurrences of digits?

I want to count each numeral(0 through 9) of occurrences of digits in the range $[1, n]$. Note that 101 has two one and one zero. For example, if $n$ equals $11$: ...
1
vote
3answers
88 views

Can transcendental to the power transcendental be rational?

Can a transcendental number to the power of a transcendental number be a rational number?
-2
votes
1answer
26 views

Least quadratic Non residue [closed]

What are all results known yet using without using riemann hypothesis on the bounds on Least quadratic non residue .
2
votes
0answers
31 views

Titchmarsh S function

SO it is known that Titchmarsh S function $$ S(T)= \pi^{-1} arg\quad \zeta\bigg(\frac{1}{2}+iT\bigg)$$ under the assumption of *riemann hypothesis * gives $$ S(T)=O(\frac{\log T}{\log \log T})$$ can ...
2
votes
0answers
21 views

Show that $\gcd(x_1,…,x_k,x_{k+1})=\gcd(\gcd(x_1,…,x_k),x_{k+1})$

I would really appreciate if you could check my proof. Thank you. Show that $\gcd(x_1,...,x_k,x_{k+1})=\gcd(\gcd(x_1,...,x_k),x_{k+1})$ Let $\gcd(x_1,...,x_k,x_{k+1})=a$. We first show that $a$ ...
1
vote
1answer
30 views

Group of Dirichlet Characters Modulo $q$ is Isomorphic to $(\mathbb{Z} / q\mathbb{Z})^*$

I'm currently reading a book on analytic number theory, and shortly after defining Dirichlet characters, the author stated that one can prove that for a given $q\in\mathbb{N}$, the group of Dirichlet ...
2
votes
2answers
35 views

When is Chebyshev's $\vartheta(x)>x$?

Various bounds and computations for Chebyshev's functions $$ \vartheta(x) = \sum_{p\le x} \log p, \quad \psi(x) = \sum_{p^a\le x} \log p $$ can be found in e.g. Rosser and Schoenfeld, Approximate ...
1
vote
1answer
17 views

prove a function is not one-to-one

Let us look at the field $\mathbb{F}_{p}=\{0,1,2,...,p-1\}$ for a prime number p. And let $f:\mathbb{F}_{p}\rightarrow \mathbb{F}_{p}$ be the function given by $f(n)=n^2 \space (mod \space p)$. How ...
4
votes
1answer
91 views

How do I prove that the recurrence contains no perfect square?

Given the recurrence $$a_{n+2} = 14a_{n+1} - a_n - 6$$ with $a_1=1$ and $a_2=8$, how do I prove that none of the $a_n$'s apart from $a_1$ is a perfect square. This is not a homework problem, rather ...
0
votes
0answers
29 views

Diophantine eqution with a parameter

My question is about the problem when is the number $$\frac{m^3 + n^3}{n^2+m^2+m+n+c}$$ a natural number. Here $c\in \mathbb{N}$ is a constant and $m, n \in \mathbb{N}$ are the variables. This ...
-2
votes
0answers
39 views

How to uniquely write integers in rational bases

If we wish to write 13(decimal system) on base 3 system we would write it as: (1)*3^2 +(1)*3^1 +(1)*3^0 = 111(base 3) What happens if we wish to write the same number (13) in a system that uses a ...
0
votes
1answer
10 views

Solving a congruence with an invertible piece

If I have $$a \equiv bp^k \bmod p^e$$ for $0 \leq k \leq e$ with $a,p,k,e$ known. How do I solve for $b$ given that $b$ is invertible?
0
votes
0answers
29 views

Open conjectures in number theory that is easy to do some programming for

I have a to do a project in number theory that we are assigned that we should do some programming for that is not the collatz conjecture, so any suggestion would be really great.
1
vote
1answer
62 views

Number of real embeddings $K\to\overline{\mathbb Q}$

How many real embeddings, $K\to\overline{\mathbb Q}$ with $K=\mathbb Q\left(\sqrt{1+\sqrt{2}}\right)$ are there ? We set $f(x)=x^4-2x^2-1$ and if $\alpha=\sqrt{1+\sqrt{2}}$ then $f(\alpha)=0$. ...
0
votes
2answers
40 views

Hensel’s Lemma Number Theory Confusion

I have been given an example, finding the solutions of the congruence $f(x) ≡ 0$ (mod $5^4$) for $f(x)=x^2+1$ This solution finds that for mod $5$ we have $x_0=2$ . So through the 'lifting' process, ...
-1
votes
3answers
84 views

Interesting question in internet [duplicate]

Is this even possible to solve? 30 is an even number. I don't think there's Answer for this .
1
vote
3answers
66 views

Is the following a number field?

Is the field obtained by adjoining all the cube roots of $-3$ to $\mathbb Q$ a number field ? The cube roots of $-3$ are: $-\sqrt[3]{3},\sqrt[3]{3}e^{\frac{i\pi}{3}}, ...
0
votes
0answers
28 views

Fast algorithm to invert a large sparse matrix

I am interesting in sparse matrix that defined at here. I am looking for a fast algorithm to invert the matrix (better than Gaussian Elimimation). Could you suggest to me some methods that reduce ...
2
votes
1answer
85 views

Asymptotics for square-free numbers in an arithmetic progression

Set $$Q(s,\chi)=\sum_{n=1}^{\infty}\frac{\mu(n)^2\chi(n)}{n^s},\quad (s=\sigma+i\tau),$$ where $\chi$ is a character $\mod q$, Show that $Q(s,\chi)=L(s,\chi)H(s,\chi)$ where $H(s,\chi)$ is a ...
3
votes
0answers
63 views

How prove $\sigma(4^p-1)<(2^{p+1}-1)^2$

If $p$ is an odd prime numbers, show that $$\sigma(4^p-1)<(2^{p+1}-1)^2$$ where $\sigma(n)$ stands for the sum of divisors. I thought of using the formula for $\sigma(n)$: If ...
2
votes
1answer
55 views

Elliptic Function

Let $y$ be the function defined by $$y(\theta)=2sin\frac{\theta}{2}\prod_{k=1}^{\infty}\frac{(1-e^{i\theta}q^k)(1-e^{-i\theta}q^k)}{(1-q^k)^{2}}$$ where $q = e^{2\pi i\tau}$ Show that $y$ has simple ...
2
votes
1answer
21 views

Logarithm of the n'th prime.

Let $P_n$ denote the n'th prime number. How could we conclude the following from the prime number theorem? $$ \log(P_n)=\log n + \log\log n + o(1) $$ Maybe by showing that $P_n=An\log n $ for a ...