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)

0
votes
1answer
11 views

Does the natural (asymptotic) density of a set A change if a subset of A with natural density zero is subtracted from A?

I know that given two subsets of the Naturals A and B, if the natural density of A equals some non-zero real number a, and the natural density of B is zero, then the natural density of the symmetric ...
3
votes
2answers
85 views

Solve $p^3=p^2+q^2+r^2$ where $ p , q $ and $r$ are prime numbers.

The question is pretty self-explanatory.I was wondering how this equation could be solved using "number theory".
0
votes
2answers
149 views

Proving $x^{2}+1 \neq n! $,using Gaussian Integer.

I want to show that $$x^{2}+1 \neq n! $$ for $n>3$ where $x,n$ are both integers. Since $$x^{2}+1=(x+i)(x-i) $$ it follows that $x^{2}+1$ has only prime factors on the form ($4k+1$), whereas $n!$ ...
0
votes
1answer
23 views

How find this system equation with Euler's totient function

Let $f(n)$ is smallest the positive integers greater than $n$ that are non-Coprime to $n$, in other words, $f(n)=\{(f(n))_\min\mid\gcd(f(n),n)>1,f(n)>n\}$ solve this following system ...
-2
votes
1answer
76 views

Expected number of numbers chosen. [closed]

Given $n$ persons in a line, if each person chooses randomly any of the integer from $1$ to $n$, given his number is not equal to the integer which the previous and next persons have chosen. For each ...
0
votes
2answers
25 views

Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$. Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv ...
-1
votes
0answers
26 views

Modular Multiplicative Inverse of a Number

Modular Multiplicative Inverse for a prime M A^(M-1) % M = 1 From Fermat's Little Theorem Hence, A * A^(M-2) % M = 1 Or in other words, A^-1 % M = A^(M-2) % M ...
2
votes
1answer
51 views

Number Theory : Is a complete residue system modulo $n$ a group?

I was working my way through some basic number theory problems, when in the chapter on "Introduction to Group Theory," I came across the following: Show that for every positive integer $n$, the ...
-2
votes
0answers
50 views

Fastetst method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$

Is there any faster method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$? Lucas theorem is also turning out to be slow! $a,b\leq10^9$ and $m=10^6+3$.
1
vote
2answers
29 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
32 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
79 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
52 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
52 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
36 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 ...
0
votes
2answers
27 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
27 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
64 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
92 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 ...
-1
votes
1answer
44 views

Prime number (Product of prime number) [closed]

Is the product of prime numbers must be prime number or must not be prime number? Can someone prove the answer or give a brief explanation? Thanks .
-1
votes
0answers
47 views

No. of paths in a Table [closed]

There is a table of size R×C; R rows and C columns. A sub-rectangle of the table is blocked. We are only able to move right or down. What is the number of paths from the upper-left cell to the ...
-1
votes
0answers
39 views

Poles ans Zeroes [closed]

If Let $f$ be the function defined by $$f(x)=2sin\frac{x}{2}\prod_{k=1}^{\infty}\frac{(1-e^{ix}q^k)(1-e^{-ix}q^k)}{(1-q^k)^{2}}$$ where $q = e^{2\pi it}$ If $g(x)=\frac{f(2x)}{f^4(x)}; \quad \quad$ ...
3
votes
2answers
62 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
48 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
32 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
96 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
62 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
85 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
25 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
28 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
34 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
86 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
28 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 ...