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
3answers
32 views

Palindromic numbers, and $3$. [closed]

Let $x \in \mathbb{Z}$, and $x'$ be the palindrome of $x$. Why is it that $3 \mid (x - x')?$
1
vote
0answers
79 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
0
votes
0answers
53 views

How to find the number of subsets of a set $X$ such as the sum of their elements is divisible by 3?

Let $X$ be a set with $N$ numbers ($N$ is less than 1000). The problem is to find the number of subsets of $X$ such that the sum of their elements is divisible by 3. Lets denote this number by ...
9
votes
1answer
115 views

Integer solutions to the equation $a_1^2+\cdots +a_n^2=a_1\cdots a_n$

What is the general solution to the equation $$\sum_{j=1}^n a_j^2=\prod_{j=1}^n a_j,$$ $n\in \mathbb N$ , $n \ge 2$ over $\mathbb N_0$ ? WLOG, we can assume $0\le a_1 \le a_2\le \cdots \le a_n$ For ...
2
votes
0answers
80 views

Project Euler Problem #87 - Prime power triples

I found this problem in Project Euler: https://projecteuler.net/problem=87 The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is $28$. In fact, ...
1
vote
1answer
18 views

Does the field norm commute with field morphisms?

Consider a field extension $K$ of $\Bbb{Q}$, a finite extension $L$ of $\Bbb{Q}_p$ for some fixed prime number $p$, and a field morphism $\sigma \colon K \to L$ such that the diagram $\require{AMScd}$ ...
1
vote
1answer
20 views

$\Gamma_0(4)$ has no torsion except $-1$

Let $\Gamma_0(4)$ be a congruence subgroup of $SL(2,\mathbb{Z})$ defined as $$\Gamma_0(4)=\{M=\begin{pmatrix} a &b\\ c& d \end{pmatrix}\in SL(2,\mathbb{Z})\mid c=0\bmod 4\}.$$ How to prove ...
4
votes
1answer
30 views

$L(1,\chi) = \sum_{n=1}^{\infty}\frac{\chi (n)}{n} > 0$, for $\chi$ be the non-trivial real character

Let q be an odd prime and $\chi$ be the non-trivial real character modulo q. I am trying to prove that $L(1,\chi) = \sum_{n=1}^{\infty}\frac{\chi (n)}{n} > 0$. Note: this question was first asked ...
0
votes
2answers
41 views

Proving if $-1 < x < 1$ then $x^1 + x^2 + \cdots + x^n = \frac{x-x^{n+1}}{1 - x}$

Let $$S_n = x + x^2 + x^3 + \cdots + x^n$$ then $$xs_n = x^2 + x^3 + \cdots + x^n + x^{n+1}$$ This is taken from book "An concise introduction to pure mathematics" : Why does inserting $x$ to ...
0
votes
0answers
43 views

a question designed in number theory

sorry my friends I designed a question that I know the answer of but I don't know if it is a good question or not. Maybe the answer of this question is trivial. If it is possible give me your ...
3
votes
1answer
38 views

Elliptic curves, reduction map, $E_n$

Let $E$ be the elliptic curve and set $\phi: E(\mathbb{Q}_p) \rightarrow E(\mathbb{F}_p)$ to be the reduction morphism. Define $E_n := \{(x:y:z) \in \ker \phi | x/y \in p^n\mathbb{Z}_p\}$. I'm busy ...
1
vote
1answer
23 views

Clarification of a proof of Eisenstein's lemma

I'm working on a proof of quadratic reciprocity following Wikipedia's proof via Eisenstein, and one line in the proof seems unjustified: On the other hand, by the definition of $r(u)$ and the ...
2
votes
1answer
37 views

Is the Champernowne constant an automatic number?

The Champernowne constant in base $b \geq 2$ is obtained by concatenating the $b$-ary expansion of every integer. For example, in base $10$ this is $$ 0.123456789101112131415\dotsc $$ Question: Is the ...
0
votes
1answer
43 views

Subset Sum Problem (general)

I have a problem which turned to be similar to the Subset Sum Problem. The main differences between the Subset Sum Problem and my problem are: 1- The vector elements can be positive and negative (in ...
3
votes
0answers
18 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
3
votes
2answers
98 views

Why is $\sigma_1(0)$ not $-\frac{1}{12}$?

The Eisenstein series $\mathbb{G}_2$ is given by $$\mathbb{G}_2(z) = -\frac{1}{24} + \sum_{n=1}^\infty \sigma_1(n) q^n$$ with $q=e^{2\pi i z}$ and $$\sigma_1(n):=\sum_{d\mid n} d$$ for $n\in\mathbb ...
1
vote
1answer
43 views

Average patients waiting time in dental office

At a Dental Office, patients come in at the rate of 20 per hour and, on average, are processed at the same rate. Patients wait in a queue till they are called up to the counter for registration. After ...
2
votes
1answer
41 views

Coefficient in the Fourier expansion of the cusp form

Ideal of cusp for $\Gamma_{0}(4)$ is principal and generated by $f(z)=η(2z)^{12}=q+\sum a(n)q^n $, this is discussed here. How one can compute the coefficient $a(n)$ when $n$ is rather large ? for ...
1
vote
0answers
38 views

How to solve the equation $x^2+Dy^2=\alpha$ over finite fields

It is known that the equation $x^2+Dy^2=1$ is solved over finite fields $\mathbb{F}_q$ and we can point out the solutions . I wonder can we give solutions for the equation $x^2+Dy^2=\alpha$ for any ...
0
votes
3answers
78 views

Proving “The sum of n consecutive cubes is equal to the square of the sum of the first n numbers.”

From http://www.themathpage.com/aPreCalc/mathematical-induction.htm states : should : not be : $$1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^3+(n + 1)^3}{2^3}$$ as everthing to left of equation is ...
3
votes
2answers
422 views

Is it a composite number? [duplicate]

How do I prove $19\cdot8^n+17$ is a composite number? Or is that number just a prime? So I tried to find a divisor in the cases $ n = 2k $ and $ n = 2k + 1 $. But I had no success. Do you have any ...
-3
votes
2answers
72 views

What is the largest 2-digit prime factor of the integer $\binom{200}{100}$ [closed]

What is the largest 2-digit prime factor of the integer $\dbinom{200}{100}$?
2
votes
5answers
111 views

Prove that if $n^2$ is odd then $n$ is odd?

Here is my solution: I assume $n^2$ is odd then I put $n^2$= $(2x-1)^2$, now I am taking root square for both sides: $\sqrt{(n^2)}$ = $\sqrt{(2x-1)^2}$ $\Rightarrow$ $n = (2x-1)$ $\Rightarrow$ $n$ is ...
1
vote
0answers
43 views

Is it true that $(1+\varepsilon)\pi(x+y)\ge\pi(x)+\pi(y)$?

Recently I was going through Udrescu's result concerning the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$ which states that ($\pi(x)$ denotes the prime counting function), For all $\varepsilon>0$ and ...
0
votes
1answer
22 views

Proving that a binomial coefficient involving a power of $2$ is even

In the process of proving that the polynomial $x^{2^n} + 1$ is irreducible in $\mathbb{Z}[x]$, I am getting stuck on proving an intermediate result: Denote $f(X)=X^{2^n}+1.$ By a linear change of ...
0
votes
3answers
80 views

How to find number which is greater?

I have two numbers $\left(\frac{8}{7}\right)^{\frac{7}{8}}$ & $\left(\frac{9}{8}\right)^{\frac{8}{9}}$. How to find out the greater number? I am 12th grad. thanks for your help.
4
votes
2answers
56 views

Help with proving that the torsion subgroup of $y^2=x^3+x$ is $E(\mathbb{Q})_{tors} \cong \mathbb{Z}/2\mathbb{Z}$

Let $E: y^2= x^3 + x$ be an elliptic curve over $\mathbb{Q}$. I'm trying to prove that $E(\mathbb{Q})_{tors} \cong \mathbb{Z}/2\mathbb{Z}$. In order to do that, I've already shown that ...
0
votes
0answers
19 views

References for Dirichlet characters and L-functions

I am working on some exercises from my Analytic Number Theory course regarding Dirichlet characters, and I was wondering if someone could provide some references for this. Here's a problem that I'm ...
4
votes
2answers
38 views

Primitive $p^n$-th root of unity in $\bar{\mathbb{Q}}_p$.

I am trying to solve the following exercise in Koblitz's "$p$-adic Numbers, $p$-adic analysis, and Zeta-Functions". Let $p$ be a prime. Let $a$ be a primitive $p^n$-th root of unity in ...
5
votes
1answer
30 views

Prove that given graph consisting of vertices numbered with composite numbers is not eulerian

We have the following graph definition: $$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ are composite numbers) $$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ are connected if and only ...
1
vote
3answers
51 views

Solutions of $y^2 = \alpha$ in $\mathbb{F}_{19}$

So I'm working on an exercise for elliptic curves and in one of my steps I have to determine all numbers $y \in \mathbb{F}_{19}$ for which it holds that $y^2 = \alpha$, with $\alpha \in ...
7
votes
1answer
82 views

On the solvability of the negative Pell equation $x^2-2py^2 = -1$

Given prime $p=8n+1$. Then $$x^2-2py^2 = -1\tag1$$ is not solvable for, $$p_1= 17, 73, 89, 97, 193, 233, 241, 257, 281, 337, 353, 401, 433, 449, 577, 593,601, 617, 641,\dots$$ but is solvable ...
2
votes
0answers
74 views

Does the Euler product for the Dirichlet $\beta$-function converge for all $\Re(s)>\frac12$?

The Dirichlet $\beta$-function is defined for $\Re(s)>0$ as: $$\beta(s) = \sum_{n=0}^\infty\frac{(-1)^n}{(2n+1)^s}$$ It has the following Euler product (I used that Dirichlet character ...
2
votes
0answers
19 views

What is binary norm of quadratic fields of sum of two squares such that one of them is necessarily even like $a^2 +4b^2?$

I am trying to simplify an expression which I have reached, suppose a number can be represented in the form of $D=a^2 + 4b^2$. What is binary norm of $D$, or how else can it be represented?
6
votes
1answer
35 views

Where $ax + b$ prime infinitely often, is $ax + b - 2$ semiprime at least once?

I'm trying to figure out a way to prove this: Given arithmetic progression $ax + b$ where $a$, $b$ coprime and $ax + b$ is prime infinitely often, it is the case at least once that $ax + b - 2$ is ...
6
votes
1answer
63 views

Is there any general method for solving $(a_1+a_2+..a_n)^2=a_1^3+a_2^3+…+a_n^3$ in positive integers $a_1,a_2,…a_n$?

We know the identity $(1+2+...+n)^2=1^3+2^3+...+n^3$ . So I was thinking , for given $n\in \mathbb N$ , is there any general method for solving $(a_1+a_2+..a_n)^2=a_1^3+a_2^3+...+a_n^3$ in positive ...
-1
votes
1answer
36 views

A question on polynomial congruence

If $m\ne 4$ is a composite number, then does there exist two integers $a$ and $b$ which, divided by $m$, give a remainder different from zero and such that if $f(x)$ is a polynomial with integral ...
1
vote
1answer
53 views

$P(n)$ is the product of two digits in the integer $n$

$P(n)$ is the product of two digits in the integer $n$. For example, $P(18)=1\cdot8=8$ $P(50)=5\cdot0=0$ $P(99)=9\cdot9=81$. Is there any nice way to find the value of ...
1
vote
1answer
27 views

Asymptotic solution for p-adic order of n! for all primes

Let v_p(n) denote the p-adic valuation of n. The number of times that a prime p appears in all numbers <= n is given by: $$ \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} ...
1
vote
1answer
44 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
1answer
71 views

Is this quantity possible?

I need help for my problem. A set $M$ of $2015$ positive integers has the following condition: if $x_1 < x_2 < ... < x_n$ are elements of $M$ with $1 \leq n \leq 2015$, then neither ...
2
votes
0answers
69 views

Pairs of $x$ and $y$

Here is my problem: Find all pairs of integers $(x, y)$ for which $x^2 - y$ and $y^2 - x$ are squares. Thanks for your and your suggestions.
-2
votes
1answer
69 views

$\exists a,b,c$ such that: $c^2|a^2+b^2$ [closed]

I have to prove that for any $n\geq 2$, there are three distinct integers $a,b,c$ in the interval $[n^2,(n+1)^2]$ such that $c^2 \mid a^2+b^2$.
-1
votes
0answers
24 views

Looking for a proof of the result that every positive integer can be written as a sum of three triangular numbers [duplicate]

I am looking for a proof of the result that every positive integer can be written as a sum of three triangular numbers . Any reference link will also be appreciated . Please help . Thanks in advance . ...
5
votes
1answer
72 views

Question about terminology in number theory

The following transformation appears often in number theory: $$F(x) = \sum_{n \le x} f \left( \frac{x}{n} \right)$$ What is the name of this transformation? PS. I will accept as answer something ...
1
vote
7answers
100 views

find the last digit of $347^{61}$

I need help with the question, "find the last digit of $347^{61}$" . I don't know where to start, I know that it requires modulo arithmetic but I can't think where to start, this is all the question ...
16
votes
3answers
1k views

Why do graph degree sequences always have at least one number repeated? [duplicate]

Why do graph degree sequences always have at least one number repeated? $(1, 2, 2, 3)$ = Valid, as you can see, because the $2$ is repeated. $(1, 2, 3)$ = Not possible to construct a graph with ...
1
vote
0answers
29 views

Is this polynomial irreducible over the rationals?

Prove (or disprove): Define $T_n(x)$ as the Chebyshev polynomial of the first kind with degree $n$. If $p$ is an odd prime, then $\sqrt{\frac{T_p(x)-1}{x-1}}$ is an irreducible polynomial over the ...
0
votes
1answer
36 views

Multiplication modulo $n$

I encountered the following basic encryption scheme while studying MIT OCW's 6.042 course: Exchange a public prime $p$ and a secret prime $k'$. Encryption: Compute $m'=rem(mk, p)$ ...
7
votes
1answer
54 views

Distribution of random divisor sums modulo n

Let $k$, $n\ge 2$ be positive integers, and choose $\ell$ such that $0\le \ell \le k-1$. For each integer $2\le j \le n$, choose a divisor $d_j$ of $j$, uniformly at random from the divisors of $j$. ...