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)

3
votes
1answer
135 views

Infinite sum of powers of the prime zeta function

denote by $\zeta_{p}(s)$ the Prime Zeta Function. Now, consider the infinite sum: $$D(s)=\sum_{n=0}^{\infty}\zeta_{p}(s)^{n}=\frac{1}{1-\zeta_{p}(s)}\;\;\;\left | \zeta_{p}(s)\right|<1$$ $D(s)$ ...
-2
votes
3answers
83 views

Show that: if $ 5\mid2n+1$ then $25\mid 14n^2+19n+6 $

Show that: if $ 5\mid(2n+1),\; $ then $25\mid (14n^2+19n+6) $. [Note: $\ $ was $\,\ 5\mid (2n\color{#C00}- 1)\,\ldots$ in original version. Some answers and comments below give counterexamples to the ...
0
votes
1answer
162 views

Prove that $p\mid \binom{p}{k},\ 0< k< p$

Prove that: $$p \,\,\left|\, {p \choose k} \right., \quad 0< k \lt p$$ if $p$ is prime. how to prove that with direct proof?
4
votes
2answers
79 views

Question about number theory asymptotic proof

Let $d(m)$ denote the number of divisors of $m$ and let $N$ be a large integer. Then we have $$\sum_{n \leq N}\frac{d(n)}{n} \geq \left(\sum_{n \leq \sqrt{N}}\frac{1}{n}\right)^{2} \sim \log^{2}N.$$ ...
2
votes
1answer
140 views

Cyclotomy in extensions of $\mathbb{Q}_p$

Let $p$ be a prime number and $K$ be a finite extension of $\mathbb{Q}_p$. Denote by $\zeta_{p^n}$ a primitive $p^n$-th root of unity (where $n$ is a positive integer). Assume that $K$ contains ...
1
vote
4answers
164 views

Question 2 On Congruence

Solve the following system of congruences: $$x \equiv 2 \pmod 5$$ $$x \equiv 1 \pmod8$$ $$x \equiv 7 \pmod 9$$ $$\quad x \equiv -3 \pmod {11}$$ i have no idea how to go about starting this, any ...
1
vote
1answer
92 views

Solution count of quadratic form congruence over $\Bbb Z / 8 \Bbb Z$

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the ...
0
votes
2answers
273 views

Euler $\Phi$ Function

I have the question: compute $\phi(24)$ for each element Z/24 decide whether the element is a unit or a zero divisor, if the element is a unit divisor give its order and find its inverse. Ive worked ...
2
votes
2answers
557 views

Sum of two squares $n = a^2 + b^2$ [duplicate]

Possible Duplicate: Prove that $n$ is a sum of two squares? Fermat’s theorem on sums of two squares Is there any elementary proof for this theorem: A number $n$ is a sum of two squares ...
1
vote
0answers
145 views

Number of solutions to polynomials over finite fields

Let $m = p_{1}p_{2}\cdots p_{s}$. Let $N_{f}(n)$ denote the number of solutions to $f \equiv 0 \pmod{n}$. If $f = f(x)$, a polynomial in the single variable $x$, then from the Chinese Remainder ...
1
vote
2answers
86 views

How do you prove a Quadratic Residue?

Help Someone please. Prove or disprove: 28 is a quadratic residue (mod 65).
0
votes
1answer
57 views

Let b,b_1,b_2 be odd, positive integers and a, a_1, a_2 ∈ Z. Prove:

Let $a,a_1,a_2$ be integers and $b,b_1,b_2$ be odd positive integers. Prove $(a_1a_2 / b) = (a_1/b)(a_2/b)$ Prove $(a / b_1b_2) = (a/b_1)(a/b_2)$ I need to prove these 2, i know both deal with the ...
6
votes
1answer
323 views

Finding the units in $\mathbb{Z}[\sqrt[3]{2}]$ and other questions

I'm reading a paper in which they solve the equation: $$a^3-2b^3=\pm 1$$ in integers using algebraic number theory. The number $a-b\alpha$, with $\alpha=\sqrt[3]{2}$, is a unit in ...
2
votes
1answer
96 views

Is there a way to rewrite this without the ceil() function?

$$L = \left\lceil \frac{\sqrt{v-4 \times N}-1}{4} \right\rceil$$ This is a line in my program but I cannot get ceil() to work in GMP, so I'd like to approach this mathematically and just rewrite it ...
2
votes
1answer
33 views

Counting points in a box modulo a number

Consider the positive integers $\leq x$, then we know that there are $x/p + O(1)$ integers $\leq x$ that are $a \pmod{p}$ ($p$ prime). Consider a similar problem, except this time, we are counting ...
1
vote
1answer
109 views

How can I find this result modulo $10^8$?

Let $\;\;\displaystyle x=\left \lfloor\frac{\sqrt{4N+(2a+1)^2}-1}{4}\right\rfloor\bmod10^8 \;\;\text{ where}\; N,a \text{ are integers.}$ When $N$ and $a$ are sufficiently large, this expression ...
2
votes
2answers
257 views

Infinitely many primes in the ring of integers

Let $K$ a number field, such that $\mathcal{O}_K= \mathbb{Z}[\alpha]$ for some $\alpha$ algebraic integer. Prove that there are infinitely many primes $\mathcal{P} \in \mathcal{O}_K$, such that ...
1
vote
1answer
431 views

Self-conjugates of a partition n

Does anyone know of an efficient way to find all self conjugates of a partition n? I know that I could guess and check using Ferrers Diagrams and following some basic rules (same number of rows as ...
6
votes
1answer
391 views

Edmund Landau's Problems

Landau's problems are four conjectures about prime numbers which were unsolved at the time Edmund Landau presented them at the International Congress of Mathematicians in 1912. They include: ...
2
votes
1answer
242 views

Gauss sum for primitive real Dirichlet character

If $\chi$ is a real non-trivial primitive character modulo $q\ge 1$, then how could one show that $$\sum_{n\in \mathbb Z/q\mathbb Z} \chi(n)e\left(\frac nq\right) = \sum_{n\in \mathbb Z/q\mathbb Z} ...
8
votes
1answer
156 views

Summation over relatively prime numbers

Why is it true that $$\frac{\varphi(m)}{m}\sum_{n \leq x}\frac{1}{n} \leq \sum_{n \leq x, (n, m) = 1}\frac{1}{n}?$$ Intuitively to see this, one can think of that from 1 up to $m$, there are ...
0
votes
2answers
36 views

Determining thresholds based on value of variable

All variables here are integers. $$z^2=x^2+4y$$ I am trying to generate all $x,y$, given valid ranges $1\leq x\leq N$ and $-N\leq y\leq N$ intelligently. Basically, given a selection of $x$ from 1 ...
1
vote
0answers
144 views

solution count of quadratic form congruences

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the ...
1
vote
1answer
67 views

Arithmetic function inequality

Fix integers $n$ and $k$. Why is $$\sum_{\substack{d < n\\(d, k) = 1}} \frac{\mu(d)^{2}}{\varphi(d)} \geq \sum_{\substack{d < n\\(d, k) = 1}}\frac{1}{d}?$$
6
votes
4answers
277 views

Given $a + \sqrt{b}$ with positive integer $a,b$, find $a$ and $b$?

Suppose I had $n = a + \sqrt{b}$ as a decimal of arbitrary precision, but didn't know $a$ or $b$, except that they are positive integers. If I had just $\sqrt{b}$, I could just square it and end up ...
7
votes
1answer
143 views

Are there infinitely many pairs of rational numbers such that…

Are there infinitely many pairs of rational numbers $(a,b)$ such that $a^3+1$ is not a square in $\mathbf{Q}$, $b^3+2$ is not a square in $\mathbf{Q}$ and $b^3+2 = x^2(a^3+1)$ for some $x$ in ...
1
vote
3answers
553 views

Is there an equation for the sum of alternating cubes?

The following sequences for sum of alternating cubes: Odd cubes: [1, 28, 153, 496, 1225, 2556, 4753, 8128, 13041, 19900, 29161, 41328, 56953, 76636, 101025, 130816, 166753, 209628, 260281, 319600] ...
3
votes
1answer
159 views

What is this pattern in the Euclidean algorithm?

I was playing around with the Euclidean algorithm when I noticed the following. Assume that some number $r_1$ breaks down via the Euclidean algorithm as follows: $$ r_1 = q_1r_2 + r_3 \\ r_2 = ...
2
votes
0answers
116 views

Integral of product of two square waves over [0,1]

In Mathematica notation, I am looking for the function f[m,n] for real numbers m and n defined by f[m_,n_]:=Integrate[SquareWave[m x]SquareWave[n x],{x,0,1}]. I'm trying to get a closed form for the ...
-4
votes
1answer
174 views

Sequences and lottery tickets

Let's have the following sequence of natural numbers $4, 5, 7, 9, 11, 14, 16, 20, 22, 27, 29, 35,...a_n,a_n+1$. Does anyone know which two consecutive terms of this sequence have a ratio ...
1
vote
2answers
84 views

Function expansion help

I want to write a function, $f(k,a,b)$, I made, in terms of combinations of the fractional part function, $$ j\left\{\frac{c \ }{d}k\right\},$$ where $c,d,$ and $j$ are any integers. The function is ...
3
votes
2answers
187 views

Set of sum of cosines is finite

Let $x,y \in \mathbb{R}$ such that the set $\{\cos{(n\pi x)} + \cos{(n\pi y)} | n \in \mathbb{N} \}$ is finite. Show that $x$ and $y$ are rational. I have been trying to consider a graph of this set ...
2
votes
1answer
53 views

Finding an equation of solutions of an equation given constraints

$$\left(\frac{ax}{p_1}\right)^2 - \left(\frac{bx}{p_2}\right)^2 = cx \quad\text{and}\quad a\neq p_1, \, \, b \neq p_2$$where $a,b,c$ are nonzero integers, and $p_1$ and $p_2$ are distinct prime ...
1
vote
1answer
225 views

Field construction

Explain how to construct a field of order $343$ not using addition and multiplication tables. I understand that every finite field has order $p^n$ for some prime $p$. Since $343$ is $7^3$, let ...
2
votes
1answer
88 views

Find prime numbers $a, b, c$ such that $a^b+c$ is a prime

Please help me find all $a, b, c \in \mathbb{P}$ such that $a^b+c$ is a prime Example I just can find: $2^3 + 5 = 13 \in \mathbb{P}$
2
votes
0answers
60 views

Upper bound for non-square-free sum

Given a multiplicative function $f$, is there any general method of getting a upper bound of $\sum^{'}_{n<x} f(n)$, where the sum is restricted to all those non-square-free $n$? For example, when ...
0
votes
1answer
62 views

Generating valid x and y that result in perfect squares

$$t=x^2+4y$$ How do I generate all $x,y$ where $t$ is a perfect square greater than or equal to zero, given valid range $-N\leq x,y\leq N$? All variables here are integers.
1
vote
0answers
26 views

group law on weil-chatelet group

Is there a reference for the gemetric definition of the group law on the Weil-Châtelet group of an Abelian variety more recent than the original Weil's paper ("On algebraic groups and homogeneous ...
4
votes
1answer
152 views

Are these two facts related?

I was told some days ago that the possibility of two randomly picked numbers are relatively prime to each other is $6/(\pi^2)$. And it is well known that the value of Riemann zeta function at 2 is ...
1
vote
1answer
101 views

Prove that if a ≡ b (mod c), where c is odd, then (a/c) = (b/c)

Solution: Applying Euler's Criterion, We have (a/c) ≡ a^(c-1)/2 (mod c) Hence if a ≡ b (mod c), then (a/c) ≡ a^(c-1)/2 ≡ b^(c-1)/2 ≡ (b/c) ≡ (mod c) From here I'm not sure how to show that ...
4
votes
4answers
673 views

Evaluating a power series

Can somone help me find a closed form expression for this sum given any rational value of x, and any integer p, where {x} denotates the fractional part of x.$$\sum_ {k=1}^{\infty}\frac{ \left\{p^kx ...
9
votes
1answer
247 views

Simple matrix help

Let 'M' be an $(a-1)\times(a-1)$ coeifficent matrix, $\large\ m_{r,c}=\left\{\Large\frac{r\cdot c}{a}\right\}$ Where $\{ x \}$ is the fractional part of $x$. And let vectors 'G' and 'H' be column ...
4
votes
2answers
588 views

Bounding the prime counting function

How can I get inequalities that bound the prime counting function if I have the following inequalities for some functions $f(x)$ and $g(x)$: $$ g(x)<\psi(x)<f(x), $$ where $\psi(x)$ is second ...
1
vote
2answers
133 views

Möbius function help

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate ...
3
votes
3answers
216 views

Are there infinite many integer $n\ge 0$ such that $10^{2^n}+1$ prime numbers?

It is clear to see that 11 and 101 are primes which sum of digit is 2. I wonder are there more or infinte many of such prime. At first, I was think of the number $10^n+1$. Soon, I knew that $n\neq ...
4
votes
0answers
55 views

How to compute n choose k modulo a prime power efficiently using extended Lucas' Theorem? [duplicate]

Possible Duplicate: Lucas Theorem but without prime numbers This question mentions a strategy for computing C(n, k) modulo a composite number, but leaves out the details. The use of the ...
3
votes
1answer
533 views

how to find integer solutions for $axy +bx + cy =d$?

How can I find the integer solutions for the diophantine equations $axy +bx + cy =d$ ? the smallest particular solution ($x_0$,$y_0$) and a way to generate the rest.
3
votes
1answer
68 views

How many possible choices are there?

(French Mathematical Olympiad 1997) Each vertex of a regular $1997$-gon is labeled with an integer, so that the sum of the integers is $1$. We write down the sums of the first $k$ integers read ...
1
vote
2answers
383 views

Solve the Congruence equation

Well I had come across a problem where I have to solve the below equation . Is there any direct relation like f(k,r) = n ? How to find n for given value of k and r ? $$ 7^{n}\equiv r \pmod{10^k} \,. ...
2
votes
2answers
111 views

How to prove the divisors of two numbers is the same as the divisors of a and b?

Given $a$ and $b$ I am trying to find an informal proof that the divisors that $a$ and $b$ have in common are the divisors of the number $n$ such that $n = \gcd(a,b)$. I think it is obvious that the ...