Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

2
votes
1answer
94 views

Cauchy-Davenport theorem and its extension

According to Cauchy-Davenport Theorem, if $A,B$ are subsets of a prime field ($F_p$) then we have the following bound on the number of elements within the sumset $A + B = \left\{ {\left. {a + b} ...
2
votes
1answer
69 views

finding zeroes of a quadratic form

Let $a,b\in\mathbb Z$ be squarefree with $a>0$. Suppose that I know that there exist $(0,0,0)\neq (x,y,z) \in \mathbb Z^3$ s.t. $x^2-by^2-az^2=0$. Is there any known algorithm to find any such a ...
2
votes
1answer
91 views

The set of exponential primes

Consider a set of integers $Q$ such that the set of all positive integers $\mathbb{Z}$ is equivalent to the span of ever possible power tower $$a_1^{a_2^{\ldots a_N}}$$ involving $a_i \in Q$. In ...
2
votes
1answer
55 views

$15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$

For which numbers $a$ is it true that if $15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$? I know that this means that $a\frac{15-c}{25}=k_1\in \mathbb{Z}$ and $\frac{15-c}{25}=k_2\in \mathbb{Z}$, but ...
2
votes
1answer
31 views

$d$ to $1$ map, cyclic group and cosets

We know that $\mathbb{F}_p^{\times}$ is a cyclic group. Let $g$ be a prmitive root mod $p$, then the kernel of the map $\varphi:\mathbb{F}_p^{\times}\rightarrow \mathbb{F}_p^{\times}$ defined by ...
2
votes
1answer
201 views

Messing around with the abel-plana formula for $\sum_n \frac 1{n^3}$

I've just discovered the Abel-Plana formula: http://en.wikipedia.org/wiki/Argument_principle I'm trying to use it to get a closed-form expression for $\sum_{n=1}^\infty \frac 1{n^3}$. So far, I have ...
2
votes
1answer
94 views

projectors in a tensor product of number fields

Let $F=\mathbb{Q}(\sqrt{-d})$ be an imaginary quadratic number field and choose an ordering of the Galois group $Gal(F/\mathbb{Q})$, let us say $\{id, \sigma\}$. Then one has an isomorphism $F ...
2
votes
1answer
114 views

Inclusion Exclusion and lcm

I would like to show that for any positive integers $d_1, \dots, d_r$ one has $$ \sum_{i=1}^r (-1)^{i+1}\biggl( \sum_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i})\biggr) ~\leq~ ...
2
votes
1answer
89 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
2
votes
1answer
95 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
1
vote
1answer
60 views

Congruences of weights of modular forms modulo primes

I'm trying to prove that for two modular forms $f$ and $g$ of weight $k$ and $k'$ respectively, that are congruent modulo a prime $\ell\ge 5$, their weights are congruent modulo $\ell-1$. This is what ...
1
vote
1answer
47 views

If $n$ is a positive integer such that the sum of all positive integers $a$…

I am stuck with the following problem that says: If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1 \le a \le n$ and GCD $(a,n)=1$ is equal to $240n,$ then ...
1
vote
1answer
71 views

Number of points on an elliptic curve over $ \mathbb{F}_{q} $.

I have the following elliptic curve: $$ E: \quad Y^{2} = X^{3} + 1 ~ \text{over} ~ \mathbb{F}_{q}, ~ \text{where} ~ q \equiv 1 ~ (\text{mod} ~ 3). $$ I want to know the number of points on this curve. ...
1
vote
1answer
27 views

To find solutions of $\dfrac n{d(n)}=p$

For positive integer $n$ let $d(n)$ denote the no, of positive divisors of $n$ , then for a prime $p$ , how do we find all solutions of $ \dfrac n{d(n)}=p$ ?
1
vote
1answer
67 views

Sum of reciprocals of primes for known primes.

I was reading through some old analytic number theory notes earlier and found the interesting fact that even though $\sum\frac{1}{p}$ diverges: $\sum_{\text{known primes}}\frac{1}{p} < 4$. ...
1
vote
1answer
55 views

Number of solutions of some congruence equations.

How many $[u]\in(\mathbf{Z}/ab\mathbf{Z})^\ast$ satisfy the equations $u\equiv 1 \bmod \ a$, $u\equiv 1 \bmod \ b$? I somehow believe that the answer might be $(a,b)$. Is this actually true? Is the ...
1
vote
1answer
126 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
1
vote
1answer
84 views

Question on complete discrete valuation field.

Let $F$ be a complete discrete valuation field and $f(X) = X^n + a_{n-1}X^{n-1} +\cdots+ a_0$ is an irreducible polynomial over $F$. How to show that a) $ v(a_0) > 0$ implies $v(a_i) > 0$ for ...
1
vote
1answer
32 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
1
vote
1answer
120 views

Is my conjecture true? : Every primorial is a superior highly regular number, and every superior highly regular number is a primorial.

I have invented two sets of positive integers: highly regular numbers and superior highly regular numbers. A positive integer $m \leq n$ is a regular of the positive integer $n$ if all prime numbers ...
1
vote
1answer
47 views

$k$-Fibonacci sequence modulo $p$

Let $k$-Fibonacci sequence (generalized Fibonacci sequence) be defined as $$ F_{k,n+1} = kF_{k,n} + F_{k,n-1} \space for \space n\geq 1 $$ with initial conditions $$ F_{k,0} = 0; F_{k,1} = 1 $$ For ...
1
vote
1answer
44 views

Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
1
vote
1answer
54 views

Why does this equation work?

let $ P(x) := \sum_{p \leq x} Log [p]$, then we have $P(2^{k+1}) = \sum_{i=0}^k ( P(2^{i+1}) - P(2^i)) < 2 \cdot Log[2] \cdot (1 + 2 + 4 +... + 2^k) \leq 4 \cdot Log[2] \cdot 2^k$. Why does ...
1
vote
1answer
21 views

How can I conclude that the integers $a r_1, a r_2 … ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,…,r_{\phi(m)}$?

How can I conclude that the integers $a r_1, a r_2 ... ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,...,r_{\phi(m)}$ given the proofs that $(ar_i,m) = 1$ ($\gcd$) for every $i$ ...
1
vote
1answer
17 views

Divisor function of factorials and other integers

Is there a proof or any known value of $x$, for which $x<n!$ and $\sigma(n!)<\sigma(x)$
1
vote
1answer
23 views

Integer-handling alg0rithms

anyone has a good reference (books, websites) on optimised algorithms for integer handling - i am thinking about factorisation, primality, and number-theoretical function related problems. Optimised ...
1
vote
1answer
32 views

Finding number of solutions

What is the number of solutions to the pair of equation $\sin({x+y\over2})=0$ and $|x|+|y|=1$ Is there any general rule/formula to find out the number solutions of an equation?
1
vote
1answer
111 views

How to solve this Diophantus equation$(s^2=4m^2n^2+p^2$,$p^2=m^2+n^2)$?

$$s^{2}=4m^{2}n^{2}+p^{2}; p^{2}=m^{2}+n^{2}; 1<m<n<p<s$$ I think that this equation does not have positive Integer solution, but how to prove?
1
vote
1answer
47 views

Rational vs irrational

If two points on a number line is shown, are rational numbers between the two points is more or irrational number is more ? I have tried using probability , my collegue who was like my teacher also ...
1
vote
1answer
59 views

Solve a system of diophantine equations

I have a problem with elemental number theory. I started with the expression $$ (a - \frac{1}{b})(b - \frac{1}{c})(c - \frac{1}{a}) $$ and task to find all natural $a,b,c$ so that the result of the ...
1
vote
1answer
38 views

Concerning squarefree numbers with 2 primes and squarefrees with 3 primes.

If a squarefree with two primes is a 2-prime and a squarefree with three primes is a 3-prime is there an integer N such that the number of 2-primes less than N is equal to the number of 3-primes less ...
1
vote
1answer
21 views

Greatest common divisor and exponent relationship

For a > 1 show that the gcd$(a^n - 1, a^m - 1) = a^{(m,n)} - 1$ What are some useful equalities that might help in proving this relationship? I believe the constrains for $m,n$ are all positive ...
1
vote
1answer
60 views

Is it true that $6n^2+p$ gives primes for $n=0,1,2,\dots,p-1$ iff $Q(\sqrt{-6p})$ has class number $4$?

Let $p$ be a prime number, are the following statements true? 1.Quadratics of the form $6n^2+p$ gives primes for $n=0,1,2,\dots,p-1$ iff $Q(\sqrt{-6p})$ has class number $4$. And all such primes ...
1
vote
1answer
46 views

question on combinatorics and number theory

We have an equation as: $a\times b < n$ where $n$ is any positive integer. Now my question is how many pairs of positive integers $(a,b)$ can be found to satisfy the equation. For example, ...
1
vote
1answer
17 views

is the lattice [$2+\sqrt{11},3-2\sqrt{11}$] an ideal in $O_{11}$

Is the lattice [$2+\sqrt{11},3-2\sqrt{11}$] an ideal in $O_{11}$ $N(2+\sqrt{11})=4-11=-7$ $N( 3-2\sqrt{11} )=9-4*11=-35$ $Tr( \left(2+\sqrt{11})(3-2\sqrt{11} )\right)=56$ since ...
1
vote
1answer
20 views

On the number of midpoint free subsets

A set $X$ of real numbers is called midpoint free if whenever $x,y$ are distinct elements of $X$ then $\frac{x+y}2 \not \in X$. What is number of midpoint free subsets of $\{1,2,...,n\}$?
1
vote
1answer
66 views

How do I find an integral basis, given a basis consisting of algebraic integers?

A known example of a number field that has no power basis is the field $\mathbb{Q}(\theta)$, where $\theta$ is a root of the polynomial $x^3-x^2-2x-8$. The discriminant of this polynomial is $-2012 ...
1
vote
1answer
36 views

Reducing simultaneously a pair of fractions $\frac{a^2}{b},\frac{ a^3}{c}$ using only gcds

Given three positive integers $a,b,c$ and I want to find the smallest positive integers $a', b', c'$ such that $$ \frac{a^2}{b} = \frac{a'^2}{b'} \quad \text{and} \quad \frac{a^3}{c} = ...
1
vote
1answer
141 views

A question about prime gaps

Recently, I have been reading the Wikipedia article about prime gaps (http://en.wikipedia.org/wiki/Prime_gap) and I came across the following: Hoheisel was the first to show that there exists a ...
1
vote
1answer
51 views

How to prove that the sum digits of repetend divide by the length of the repetend equal to 4.5?

Lets m is the repetend of the reciprocal of a prime, k is number of digits of m and k is even number then the digits sum of m divide by k must equal to 4.5 Sample: 142857 is the repetend of the ...
1
vote
1answer
24 views

ramification of valuations

By a “prime” of K (number field), we mean an equivalence class of nontrivial valuations on K. What does it mean for a finite prime p to ramify in an extension L of K? I'm reading these notes ...
1
vote
1answer
68 views

Primes and infinite primes of the form

can you give the validity or proof of the following statements of my observations on Primes? $(1)$ For a positive integer $k$, there exists infinitely many primes of the form $29 + 72k$. $(2)$ If the ...
1
vote
1answer
54 views

Converse of Euler-Lucas Theorem?

The Euler-Lucas Theorem states that every factor of $2^{2^n}+1$ ($n$th Fermat number) has the form $2^{n+2}k+1$. Let $a$ be an integer. Is it true that, if every factor of $2^{2^n}a+1$ has the form ...
1
vote
1answer
54 views

Maximum number of consecutively selected rows.

You have a table, where the nth column repeats itself every p_n times (mod p_n). For example with n=5, you'd get a table like this, with the first column being mod 2, with the 5th column being mod 11: ...
1
vote
1answer
77 views

Modulus of a very large number, How to calculate $11386^{20635} \mod 31351$?

Having issues calculating mod of a very large number. Tried to check with previous examples but was unable to understand. Please help on the follow question. How to calculate $$11386^{20635} \mod ...
1
vote
1answer
45 views

$p \equiv 5 \mod8\Rightarrow p=(2x+y)^{2}+4y^{2}$

If $p \equiv 5 \mod8$ , then $p=(2x+y)^{2}+4y^{2}$,for some x and y integers. Thanks Here is my approach: I know $p \equiv 5 \mod8\Rightarrow $ $p \equiv 1 \mod4\Rightarrow $ $n^{2}+m^{2}=p\equiv ...
1
vote
1answer
50 views

Proof Check: What's the minimal n that the quadratic form $10x^2-12xy+5y^2 = n$ gets?

Firstly, I noticed that by plugging in $(1,1)$ I could get $n=3$. Next, the quadratic form is positive-definite because $a=10>0$ and $b^2-4ac = 144-4*(10)*(5) = -56 <0$. This means that the ...
1
vote
1answer
77 views

Upper bound of the jacobstahl function of primorials h(n)

This is following on from my question here: Maximal gaps in prime factorizations ("wheel factorization") The solution of my problem was the jacobsthal function applied to the product of the ...
1
vote
1answer
86 views

What is the sum of divisors of binomial&factorial

$$\sum_{m|\frac{n!}{i!(n-i)!}} m$$ Perhaps a good start is $$\sum_{m|n!} m$$ When seeing this last sum or also this one $$\sum_{m|lcm(1,2,...,n)} m$$ I sort of want to use $(n+1)n\over2$ somehow.
1
vote
1answer
62 views

How do I use the Euclidean Algorithm in the ring $\mathbb Z[\sqrt{3}]$?

I was asked to find the GCD of $7+\sqrt{3}$ and $6-2\sqrt{3}$ in the ring $\mathbb Z[\sqrt{3}]$, but have no idea where to start. Any tips would be appreciated!