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
61 views

Lower and upper bounds for the length of phi-chains wanted

For calculating $$a \uparrow \uparrow n\ (mod\ m)$$ the chain $$m , \phi(m) , \phi(\phi(m)) , \phi(\phi(\phi(m))) , ... $$ is useful. As $\phi^n(m)=1$ for some n, the above modulo calculation ...
3
votes
5answers
654 views

Proof of binomial coefficient formula.

How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$? This is an accepted fact in every book but i couldn't find a ...
3
votes
0answers
70 views

A computation modulo 1223

I want to compute $48^{306}$ modulo $1223$. I can't use a calculator, hence I tried to simplify something. I have $306=2^8+2^5+2^4+2$, thus $48^{306}=48^{2^8+2^5+2^4+2}=48^{2^8}\cdot 48^{2^5}\cdot ...
3
votes
3answers
449 views

sets with no asymptotical density over $\mathbb N$

Let's consider the Natural density on $\mathbb N$ defined by: Take $ A\subset \mathbb N$; define the sequence $x_n= \dfrac{|A\cap[1,n]|}{n}$, and then if $\lim\limits_{n\to\infty} x_n$ exists, ...
3
votes
1answer
176 views

The structure of $(\mathbb Z/525\mathbb Z)^\times$

I am working on the following problem. Find the number of the elements of order 4 in $(\mathbb Z/525\mathbb Z)^\times$. I tried to solve it in the following way: since $525=3\cdot5^2\cdot7$, we ...
3
votes
2answers
112 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
1answer
255 views

modular form -Petersson inner product

my question is about Petersson inner product. i need to prove that $(E_k,f) =0 $ $\forall f \in S_k(SL_2(\mathbb{Z}))$ the only thing that i think that should help me is that the space of cusp form ...
3
votes
1answer
676 views

Non-integer bases and irrationality

I read somewhere: When it comes to properties like prime, irrational, rational, divisible by 2, etc., nothing changes when you change base. But I'm not sure about the rational/irrational one. ...
3
votes
1answer
199 views

factorization of 2 numbers

I tried to factor the numbers $1013^{13}+331\#$ and $98!+76!+54!+32!+1$ with GMP-ECM because the quadratic sieve takes very much time. Perhaps someone factors one of those numbers for me. The second ...
3
votes
1answer
120 views

Imperfect digit-to-digit invariants in Base $10$

$3435 = 3^3 + 4^4 + 3^3 + 5^5$ is an example of a perfect digit-to-digit invariant. Fact: The number of PDDIs is finite for any given base; in particular, for base $10$. Question: Working over base ...
3
votes
3answers
157 views

Show $\mathrm{gcd}(7a+5,4a+3)=1$.

I have been trying to do this problem for a couple of days for better or worse. I suppose that $d = \mathrm{gcd}(7a+5,4a+3)$. Since $4a+3=2(2a+1)+1$ it must be that $d$ is odd. I know that $d|(7a+5)$ ...
3
votes
3answers
320 views

Defining the integers and rationals

What axiomatic system is most commonly used by modern mathematicians to describe the properties of the integers and the rationals? Properties like $a+0=a$, $a*1=a$, $a+b=b+a$, Also given these ...
3
votes
2answers
1k views

How to demonstrate that there is no all-prime generating polynomial with rational cofficents?

It seems like there is no polynomial with finite variables known, which could generate all prime numbers, by integer assignments. Is there a proof that such polynomial can not exist and does anyone ...
3
votes
2answers
96 views

natural solutions for $9m+9n=mn$ and $9m+9n=2m^2n^2$

Please help me find the natural solutions for $9m+9n=mn$ and $9m+9n=2m^2n^2$ where m and n are relatively prime. I tried solving the first equation in the following way: $9m+9n=mn \rightarrow ...
3
votes
1answer
783 views

Show that $n + 2$ and $n^2 + n + 1$ cannot both be perfect cubes

Question: If $n$ is a nonnegative integer, prove that $n + 2$ and $n^2 + n + 1$ cannot both be perfect cubes. Possible solution: Suppose $n+2$ and $n^2 + n + 1$ are perfect cubes, their ...
3
votes
4answers
584 views

divisibility of ABCD+DCBA by 11

The sum of ABCD and DCBA is always divisible by 11, where A, B, C and D are digits of a number. I understood that, ABCD = A(1000) + B (100) + C(10) + D(1) DCBA = D(1000) + C(100) + ...
3
votes
2answers
162 views

Primes for which $x^k \equiv n \pmod{p}$ is solvable

For a fixed $n$, how can I characterize the primes $p$ such that there is a $k$ with $x^k\equiv n\pmod p$? Edit: This wasn't actually what I meant... the question I intended is here.
2
votes
1answer
91 views

$\pi(x)\geqslant\frac{\log x}{2\log2}$ for all $x\geqslant2.$

Let $\pi$ be the prime counting function. Then $\pi(x)\geqslant\log x/(2\log2)$ for all $x\geqslant2.$ Maybe I am missing something pretty evident, but, so far, I have proved that ...
2
votes
0answers
105 views

Questions concerning the Integration of Integer Tetration

I've been interested in finding the antiderivative of integer tetration, a function defined as iterative exponentiation. Integer tetration is written as $^n$$x$ where $^1$$x =x$, $^2$$x =x^x$, $^3$$x ...
2
votes
1answer
64 views

How do I calculate these sum-of-sum expressions in terms of the generalized harmonic number?

I know that $$\sum_{m=2}^k\sum_{n=1}^{m-1}(nm)^{-s}=\frac 12((H_k^s)^2-H_k^{(2s)})$$ and $H_k^s=\sum_{n=1}^kn^{-s}$ But, how would I go about finding identities in terms of the harmonic number like ...
2
votes
1answer
79 views

Number $N>6$, such that $N-1$ and $N+1$ are primes and $N$ divides the sum of its divisors

The perfect number $6$ is in the middle of the primes $5$ and $7$. It is the only perfect number with this property because odd numbers are not in the middle of two twin primes and even perfect ...
2
votes
2answers
129 views

What's so special about the form $ax^2+2bxy+cy^2$?

Binary quadratic forms are sometimes studied (e.g. by Gauss) in the form $$ax^2+2bx+cy^2$$ In other words, the second coefficient is assumed to be even, and the polynomial is assumed to be ...
2
votes
1answer
415 views

Proof of Andrica when Assuming Oppermann

Proof of Andrica's conjecture by assuming Oppermann's conjecture. Oppermann's conjecture: $$n\geq2\wedge\pi\left(n^{2}-n\right) < \pi\left(n^{2}\right) < \pi\left(n^{2}+n\right).$$ ...
2
votes
1answer
154 views

Is $123456788910111121314\cdots$ a $p$-adic integer?

On the back of this question comes the natural question of whether the string $$1234567891011121314\!\cdots$$ is even a number at all. While that sort of question is vague, given the lack of generic ...
2
votes
1answer
98 views

Minimum number of ways to color each integer

I have seen this problem floating around for a while but with no answer. Since the USAMTS deadline has passed, I would really like to see an answer for this. The farthest I got with this was that $n ...
2
votes
0answers
53 views

Semiprime asymptotic step function

Since $$\pi_{(2)}(x)=\sum_{i=1}^{\pi(x^{1/2})}\left(\pi\left(\dfrac{x}{\text{p}_i}\right)-i+1\right),$$ where $\pi_{(2)}(x)$ denotes the semiprimes and $\text{P}_i$ is the $i$th prime, an asymptotic ...
2
votes
0answers
95 views

Prove the inequality for composite numbers

Is it true that $c_m+c_n$ $>$ $c_{m+n}$ for all $m$, $n$ $\in$ $\mathbb{N}$? Though the result seems true, I can't get a solution. Even the bounds on $c_n$ obtained from Prime Number Theorem ...
2
votes
2answers
86 views

A fast factorization method for Mersenne numbers

Given a prime number $p$ and a Mersenne number $M=2^p-1$: Is it true for every prime factor $q$ of $M$ that $q\equiv1\pmod{p}$? For example, $p=29$ and $M=536870911=233\cdot1103\cdot2089$: $ ...
2
votes
1answer
180 views

Existence of a simultaneous rational approximation of real numbers in (0,1)

I have a simple question the rational approximation of real vectors. Dirichlet's simultaneous approximation theorem states: Given any $d$ real numbers $\alpha_1,\ldots,\alpha_d$ and for every ...
2
votes
0answers
127 views

Will anyone check my primality test?

The proof is very straightforward and simple. We all know that all prime numbers have a last digit of 1, 3, 7 or 9, and I found that any composite number with a last digit of 1,3,7 or 9 is a product ...
2
votes
1answer
112 views

last $2$ digit and last $3$ digit in $\displaystyle 2011^{{2012}^{2013}}$

Calculation of last $2$ digit and last $3$ digit in $\displaystyle 2011^{{2012}^{2013}}$. $\bf{My\; Try}::$ for last $2$ digit:: which is same as when we divide $2011^{2012^{2013}}$ is divided by ...
2
votes
1answer
135 views

Proof on a conjecture involving $d(N)$

Let $d(n)$ denote the number of divisors of $n $. Then let $N$ be a number such that $d(N)$ divides $N$ . Also let $I= \frac{N}{d(N)}$ which is defined as the "Index of Beauty of $N$ ". Then prove ...
2
votes
2answers
306 views

Does every normal number have irrationality measure $2$?

A normal number is a number whose digit expansion in any base is "uniform" in the sense that all finite digit strings occur with the "statistically expected" frequency. I read a sentence somewhere ...
2
votes
1answer
187 views

Irrationality/Transcendentality of values of $e^{e^x}$

1) Is $e^{e^x}$ irrational for all rational $x$? It is known that $e^x$ is transcendental for every nonzero algebraic $x$. But this dos not help here because for transcedental $x$, $e^x$ can be ...
2
votes
5answers
288 views

What's so special about $e$? [duplicate]

If someone with not much mathematics in his luggage asks me: What is so special about $\pi$? then off course I have an answer. Even if $i$ would be the subject (I allready see him gazing at my ...
2
votes
1answer
98 views

Primitive root modulo $4q +1$

Let $q$ be a prime such that $ p = 1 + 4q $ is a prime as well. Show that $2$ is a primitive root modulo $p$ ( i.e. that $2$ generates the multiplicative group $( \mathbb{Z} / p\mathbb{Z})^{*}$ ) . I ...
2
votes
1answer
276 views

Kaprekar's constant-related problem

How to prove that by performing Kaprekar's routine on any 4-digit number recursively, and eventually we will get a 4-digit constant(6174) rather than get stuck in a loop, without really calculating ...
2
votes
2answers
531 views

Proving that any rational number can be represented as the sum of the each cube of three rational numbers

I found the following question in a book: Prove that any integer can be represented as the sum of the each cube of five integers. The answer : ...
2
votes
3answers
184 views

Prove that if $g$ is a primitive root of $n$ and $g*b \equiv 1 \pmod n$, then $b$ is also a primitive root of $n$.

Some useful facts I am trying to use: If the multiplicative group $U_n$ modulo $n$ is a cyclic group, a generator $g$ of $U_n$ is called a primitive root of $n$. if $g$ in $U_n$ is a primitive ...
2
votes
1answer
352 views

A convergence problem: splitting a double sum

I have been facing some difficulties with the following question. For an absolutely convergent series $\sum_m a_m$, and the Möbius function $\mu(n)$, $x=(x_1,x_2)\in \mathbb{R}^2$, and $\alpha ...
2
votes
1answer
90 views

Are there (known) bounds to the following arithmetic / number-theoretic expression?

I apologize in advance if this is something that is already well-known in the literature, but I would like to ask nonetheless (for the benefit of those who likewise do not know): Are there (known) ...
2
votes
3answers
288 views

Why the zeta function?

Why is the zeta function, $\zeta(s)$ used to obtain information about the primes, namely giving explict formula for different prime counting functions, when there are many other functions that encode ...
2
votes
1answer
216 views

Meaning of equality in zeta regularization

It is known that $$\sum\limits_{n = 1}^\infty{n = 1 + 2 + 3 + \cdots} = \infty$$ but it is also known that $$\sum\limits_{n = 1}^\infty{n = 1 + 2 + 3 + \cdots} = -\frac{1}{{12}}$$ which can obtained ...
2
votes
3answers
311 views

Sum of the Stieltjes constants? (divergent summation)

The sequence of Stieltjes-constants diverges and thus cannot be summed conventionally. However their signs oscillate (unfortunately non-periodic) and thus I tried Euler- and a version of ...
2
votes
0answers
399 views

$a^{(b^c)} \mod m$ where $c$ can be very very large

I am trying to solve the following problem. I need to find the value of $$ a^{(b^x)} \bmod m $$ where $a,b$ are integers and $$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
2
votes
0answers
501 views

Counting couples having least common multiple less than a number

Let f(n) be the number of couples (x,y) with x and y positive integers, $x\leq y$ and the least common multiple of x and y equal to n. Let g be the summatory function of f, i.e.: $g(n) = ...
2
votes
3answers
245 views

Equivalence of two characterizations of the norm of an algebraic integer.

Let $a+bi=α∈\mathbb{}[i]$ be a Gaussian integer. why is it that $N(α)=a^2+b^2$ is equal to the cardinality of $\mathbb{Z}[i]/(α)?$ My question can be generalized to quadratic integers in general, and ...
2
votes
3answers
132 views

Finding a (small) prime great enough that there are at least m elements of order m

I'm hoping that someone can provide me with some results or point me in the right direction. I'm working with finite fields; really, I'm just doing arithmetic modulo a prime $p$. I'm taking elements ...
2
votes
1answer
494 views

Prime power divisors of the fibonacci numbers

I came across a result that if $p^n \mid f_m$ for some $n\geq1$ then $p^{n+1} \mid f_{pm}$. I was wondering if this is true.
2
votes
0answers
188 views

A question on a generalization of perfect numbers

First of all, I would like to call a group immaculate provided that the orders of $G$ and $\Sigma$ (the order of $N$) where $N$ varies over all normal subgroups of $G$, are equal. From here it has ...