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
1answer
111 views

Five digit numbers where each digit can appear up to three times

The question is to determine how many five-digit numbers there are (using the digits 0-9) where each digit can appear up to three times in the number. The total number of numbers that can be made ...
1
vote
2answers
51 views

A stricter Fermat's little theorem

By Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$ for all primes p. But it is often possible to find $x$ such that $a^{x} \equiv 1 \pmod{p}$ and x < p - 1. Is there anyway to ...
1
vote
2answers
70 views
1
vote
1answer
46 views

How to compute this probability: uniform distribution of two random variables

Let $p$ be a prime number. Let $i,j \in \{1, \dotsc, p-1\}$ be fixed numbers. Let $A$ and $B$ be two random variables, where $A \in_{u.a.r} \{1,...,p-1\}$ and $B \in_{u.a.r} \{0,...,p-1\}$. ...
1
vote
1answer
55 views

How to write a general proof to prove that for all $m$, $m^n \geq n^m$

After proving $m^n \geq n^m$ for several values of $m$, it can be inferred that for every $m$ there's a $k$ such that if $n \geq k$, $m^n \geq n^m$. In other words, this can be generalized as: For ...
1
vote
1answer
43 views

Simplify a power series

I am studying bernouli numbers and I'm having trouble condensing a power series. In particular, I'm studying the equation $$b(x)^2=(1-x)b(x)-xb'(x)$$ where ...
1
vote
2answers
76 views

proportion of primes in a polynomial sequence

It is conjectured (Bunyakovsky) that when $P(x)$ is a polynomial from $\mathbb{Z}[X]$, irreducible, with positive leading coefficient and so that the integers $P(n)$ , $n\gt0$ do not share a common ...
1
vote
1answer
22 views

Typical problem on P with conditions

I am looking for prime $p$ greater than or equal to $3$ such that $p|y^2 + 4$ as well as $4|p-3$. I need simple discussion to conclude the existence of $p$. Thanks again.
1
vote
2answers
127 views

Proving the general formula [nx] where [.] is the floor function.

I've been trying to solve a exercise that asks me to prove the following generalization for the floor function: $$\lfloor nx\rfloor = \sum_{k=0}^{n-1} {\lfloor x + \frac kn \rfloor}$$ I've already ...
1
vote
1answer
46 views

Prove some properties of the $p$-adic norm

I need to prove that the p-adic norm is an absolut value in the rational numbers, by an absolut value in a field I mean a function that goes from $K \to \mathbb{R}_{\ge 0}$ such that: I)$|x|=0 ...
1
vote
1answer
86 views

If Robin's inequality ever fails, are there only finitely many colossally abundant numbers that satisfy it?

Let$\ \sigma(n)$ be the sum-of divisors function, with the divisors raised to$\ 1$. If the Riemann Hypothesis is false, Robin proved there are infinitely many counterexamples to the inequality$$\ ...
1
vote
1answer
75 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
1
vote
1answer
43 views

Maximum for $x \in \mathbb{R} $ implies supreme for $x \in \mathbb{Q}$

For an assignment I need to prove that $\sup(\mathrm{Re} (\exp(it)z) = |z| $, with $t\in \mathbb{Q}$ and $z\in \mathbb{C}$. Therefore I have first proved that $\max(\mathrm{Re} (\exp(it)z) = |z| $, ...
1
vote
3answers
691 views

Consecutive composite numbers

When I took basic number-theory course there was this exercise to find 2000 consecutive numbers. And of course it's well known that the trick to take numbers of the form $$ (n+1)!+m, \quad 2 \leq m ...
1
vote
2answers
41 views

Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits.

I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41: Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ...
1
vote
1answer
31 views

Discriminant of the characteristic equation

I want to know, what is the relationship between a matrix A and the discriminant of its characteristic polynomial. Thanks!
1
vote
1answer
61 views

Help understanding proof of Legendre's formula

Can somebody kindly help me in understanding below highlighted line in proof of Legendre's formula Particularly this step : $$ \sum\limits_{i=1}^{\infty}\left\lfloor\dfrac{n}{p^i}\right\rfloor = ...
1
vote
1answer
31 views

Can the natural numbers be defined in terms of the non-trivial zeta zeros?

Can the natural numbers be defined in terms of the non-trivial zeta zeros? Presumably they can, since $\pi(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^\rho),$ and $\zeta(s)=\sum ...
1
vote
1answer
91 views

how to show that the only rational solutions of the equation $x^4+y^4=1$ are $(0,土1), (土1,0)$?

how to show that the only rational solutions of the equation $x^4+y^4=1$ are $(0,土1), (土1,0)$ ? the hint seems like descent argument, but I can't find how to formulate the argument... Can anybody ...
1
vote
1answer
31 views

Some questions about sub-fields of the field of complex numbers

Given a sub-field $f$ of the field $\mathbb{C}$ of complex numbers, is there a name for the smallest sub-field $F(f)$ of $\mathbb{C}$ such that (1) $F(f)$ contains $f$ as a sub-field and (2) ...
1
vote
1answer
22 views

Exponention cipher - prove unique mapping from plain text to cipher text

At the heart of RSA, is the exponention cipher: C=M^e mod P (where C=ciphertext, M=Plaintext e=exponent and P=modulus.) How do you prove that two different plaintexts don't map to same ciphertext?
1
vote
1answer
37 views

Conditions for which $(\sum p_i)(\sum \frac{1}{p_i})$ over an arbitrary $i$ for a set of primes $\{p_i\}$ is unique?

I am looking for conditions (if any are needed beyond properties of primes) for which $(\sum p_i)(\sum \frac{1}{p_i})$ over an arbitrary $i$ for a set of primes $\{p_i\}$ is unique in that there is ...
1
vote
2answers
38 views

condition for tuple of non-zero integers $(a,b,c,d)$ such that $ad+bc=ac-bd=ab+cd=a^2-b^2+c^2-d^2=0$

As the title says, what would be the condition for tuple of non-zero integers $(a,b,c,d)$ such that $ad+bc=ac-bd=ab+cd=a^2-b^2+c^2-d^2=0$? Would there be infinitely many tuples that satisfy the ...
1
vote
1answer
41 views

Given a sequence, construct a function whose integral is equal to the sum of the sequence

Let $P_n$ be the sequence of prime numbers, where $P_0=2$. Given $m\in\mathbb{N}$, how can we construct $f(x)$ such that: $\displaystyle\forall{0}\leq{i}\leq{m}:f(i)=P_i$ ...
1
vote
1answer
54 views

A different way to solve Chinese remainder theorem

I'm doing my homework about Chinese remainder theorem $x = a_1(\mod n_1)$ $x = a_2(\mod n_2)$ As I know, x can be found by using: $$x=\{\sum_{i=1}^na_iN_i(N_i^{-1}(\mod n_i)) \}(\mod N)$$ with ...
1
vote
1answer
77 views

Division algorithm for the natural numbers.

I am trying to prove the following statement from Tao's analysis book. Definition of multiplication $ab++=ab+b$. Definition of addition $(a++)+b=(a+b)++$. Let $n$ be a natural number, and let $q$ ...
1
vote
1answer
64 views

Generalization for Stirling numbers 2nd kind to negative column-indexes?

The exponential generating functions for the Stirling numbers 2nd kind are the n'th powers of $f(x)=\exp(x)-1$ (where this is understood as formal power series, Abramowitz&Stegun, 26.8.12). ...
1
vote
1answer
46 views

Detail in Theorem 12 pag 33, from Marcus book “Number Field”

Let $K, L$ be number fields (i.e. subfields of $\mathbb C$ of finite degree over $\mathbb Q$) of degree $m, n$ over $\mathbb Q$ respectively and assume $[KL:\mathbb Q]=nm$. Consider $KL$ to be the ...
1
vote
2answers
35 views

Prove that the smallest integer $e$ for which $a^e$ is congruent to $1\bmod p$, where $p$ is prime, divides $p-1$.

Where e is a positive integer and p does not divide a. A question from Courant's "What is mathematics?".
1
vote
1answer
68 views

Origin of the Name 'Chernoff Sequence'

I discovered the Chernoff Sequence, $A006939$ while thinking about recreating the divisibility of $12$ and $360$. I was actually surprised to see that it already existed, and it caught my attention. ...
1
vote
1answer
28 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
1
vote
3answers
48 views

Ideals of the residual classes $\mathbb Z_n$

Let $n$ be a positive integer and considere the ring $\mathbb Z_n$ of the residual classes modulo $n$. My intuition tells me that there is no two distinct ideals of $\mathbb Z_n$ with the same number ...
1
vote
1answer
98 views

Equivalent definitions of a lattice in a real vector space of finite dimension

I'm currently trying to work my way through chapter seven of Serre's book "A Course in Arithmetic" with a view to learning about modular forms. During the course of this chapter the book begins to ...
1
vote
1answer
27 views

Evaluate the Legendre symbols (503/773) and (501/773)

Evaluate the Legendre symbols (503/773) and (501/773) my solution (501/773 ) = (((167*3))/773 ) = (167/773) * (3/773) = (773/167)*(773/3) = (105/167) * (2/3) = (3/167) * (5/167) * (7/167) * ...
1
vote
1answer
70 views

Absolute value of a cubic Gauss sum (over Field $\mathbb{F}_p$ )

I'm interested in the quantity $|\sum_{x \in \mathbb{F}_p} \omega^{ax^3+bx^2+cx}|$ where $a \in \mathbb{F}_p^*,b,c \in \mathbb{F}_p$ and $\omega$ is a primitive $p$-th root of unity i.e. ...
1
vote
1answer
55 views

How to have this equation $s^2-2(p+q+r+2pqr)s+(p^2+q^2+r^2-2(pq+qr+rp)-4)=0$?

Old Question: For $x,y,z\in N^{+}$, if such $(xy+1)(yz+1)(zx+1)$ is a perfect square ,show that $$(xy+1),(yz+1),(xz+1)$$ are all perfect square . and I konw this PDF have solution, ...
1
vote
1answer
59 views

Möbius function verification

I am looking to verify my answer to the question $$F(n)=\sum_{d|n}{\mu(d)\sigma(d)}=(-1)^{\omega(n)}\prod_{j=1}^{\omega(n)}{p_j}$$ Where $\mu$ is the Möbius function, $\sigma$ is the sum of divisors ...
1
vote
1answer
82 views

Solution to equation in surd

$\sqrt{a+b\sqrt{c}}=\sqrt{x}+\sqrt{y}$ where $a, b, c\in\mathbb{Z}^+$ and x, y $\in \mathbb{Q} $ Please help show how to disprove or prove. Thanks a lot
1
vote
1answer
63 views

When Is there no Local Power Integral Basis?

Let $A$ be a Dedekind domain, $K, L, B$ the usual designations of $A$'s quotient field, a finite separable extension of $K$, and integral closure of $A$ in $L$ respectively. If $\alpha \in B$ ...
1
vote
1answer
94 views

the average order of divisor function

In Analytic number theory by Apostol there's a theorem: $$\sum_{n\le x} \sigma(n)= \frac{1}{2} \zeta(2)x^2 + O(x\log x)$$ and then it claims that because we know that $\zeta (2)= \frac{\pi^2}{6} $ ...
1
vote
1answer
140 views

Something related to Frobenius coin Problem/Chicken McNugget Theorem

Let positive integers $a,b,c$ be pairwise coprime. Denote by $g(a, b, c)$ the maximum integer not representable in the form $xa+yb+zc$ with positive integral $x,y,z$. Prove that $$ g(a, b, c)\ge ...
1
vote
1answer
80 views

Normal number generator with digit extraction algorithm?

Are there any known ways to define an absolutely normal number (or very likely normal) number, which posses digits that can be extract via algorithm? I want to find numbers like pi that are normal and ...
1
vote
1answer
66 views

Is there a prime between $k$ and $\dfrac{11}{9}k$, $\forall k\ge 24$?

Given $k\in\mathbb{N}$, $k\ge 24$, is there always a prime number in the interval $\left[k,\dfrac{11}{9}k\right]$? I tried to verify this statement with the computer and it seems to hold. Is it ...
1
vote
1answer
70 views

Solving a Quadratic Diophantine equation for three variables

I am trying to solve the following Diophantine equation $13x^2-y^2=z^2$. Is there a standard method for generating x and y so that $13x^2-y^2$ is always a square? Mathematica gives me the following ...
1
vote
1answer
73 views

Finding formulas for sums

I know that $\sum_{d \mid n} \mu(d) = 0$ whenever $n >1$, and I know that $\sum_{d \mid n} \phi(d) = n$. How can I use this in order to give a formula for $\sum_{d \mid n} \mu(d)\phi(d)$?
1
vote
1answer
78 views

Transformation property for classical Siegel modular forms of weight 2

Let $\mathbb{H}_g = \{ \tau \in GL_g(\mathbb{C}) | \; {^t\tau} = \tau, Im(\tau) >0\}$ be the Siegel upper half space. There are Eisenstein series $$ E_{2k}(\tau) := \sum_{\gamma\in (P_0\cap ...
1
vote
1answer
68 views

another counting problem

There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of ...
1
vote
1answer
65 views

A problem on GCD

I want to calculate $f(n)$ where $f(n)$ is given by $$f(n) = \sum_{i=1}^n \dfrac{n}{gcd(n,i)}$$ and $2\leq n\leq 10^{12}$. Can someone tell me the fastest algorithm to calculate this. thanks
1
vote
1answer
49 views

Valuation associated to a non-zero prime ideal of the ring of integers

I have a question from Frohlich & Taylor's book 'Algebraic Number Theory', p.64. I will keep the notation used there. Let $K$ be a number field, $\mathcal o$ its ring of integers. Let $\mathfrak ...
1
vote
1answer
35 views

For positive intergers m an n, let $F_n=2^{2^n}+1$ and $G_m=2^{2^n}-1$. Which of the following statements are true?

For positive intergers m an n, let $F_n=2^{2^n}+1$ and $G_m=2^{2^m}-1$. Which of the following statements are true? $F_n$ divides $G_m$ whenever $m>n$. $GCD(F_n,G_m)=1$ whenever $m\neq n$ ...