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)

2
votes
1answer
307 views

Pre-Wiles' results on Fermat's Last Theorem

IIRC, there was such a result as "there is no more than 1 non-trivial solution of $x^n+y^n=z^n$, if any", wasn't it? (IIRC, Siegel theorem implies that there are finitely many solutions for $n>3$; ...
2
votes
2answers
486 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
3answers
410 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
3
votes
3answers
2k views

Pre-requisites needed for algebraic number theory

I acknowledge my limited knowledge of abstract algebra(My background comprising groups and subgroups from Herstein's Topics in Algebra is hardly worth mentioning) .And yet, I confess I really like ...
26
votes
1answer
2k views

A prime number pattern

The algorithm Given a natural number $n$ define a procedure as follows: Generate a list of primes upto and possibly including, $n$ Assign $Z = n$ If $Z > 0$, subtract the largest prime from list ...
5
votes
1answer
176 views

Statement about the order of $2$ modulo prime powers

I computed the factorization of $2^n-1$ for many $n$'s and came up with the following conjecture that for any odd prime $p$, $$ p^k || 2^n-1 \quad \Longleftrightarrow \quad O_p(2) p^{k-1} \, | \, n ...
4
votes
2answers
848 views

Keep getting generating function wrong (making change for a dollar) [duplicate]

Possible Duplicate: Making Change for a Dollar (and other number partitioning problems) I am working on the classic coin problem where I would like to calculate the number of ways to make ...
3
votes
1answer
106 views

Upper bound on smallest prime $p$ needed to tell two numbers $\leq n$ apart modulo $p$

I'm going through this paper: E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson. Remarks on separating words. ArXiv e-prints, March 2011. And on page 2, there is the following lemma: Lemma ...
7
votes
2answers
324 views

Fibonacci numbers of the form $5x^2+7$

Numerically I find the positive integer solution of the equation $F_n=5x^2+7$, where $F_n$ denotes the $n^\text{th}$ Fibonacci number, as $(n,x)=(16,14)$ and I guess that the only positive solution of ...
1
vote
1answer
106 views

Prime-base products: Plot

For each $n \in \mathbb{N}$, let $f(n)$ map $n$ to the product of the primes that divide $n$. So for $n=112$, $n=2^4 \cdot 7^1$, $f(n)= 2 \cdot 7 = 14$. For $n=1000 = 2^3 \cdot 3^3$, $f(1000)=6$. ...
6
votes
4answers
330 views

Almost a perfect cuboid

While reading a very old book on diophantine equations, I came across this exercise: Find an infinite number of positive integer solutions of the equations $$x^2 + y^2 = u^2$$ $$y^2 + z^2 = v^2$$ ...
20
votes
1answer
358 views

Combinatorial Interpretation of a Certain Product of Factorials

Let $\mu$ denote the Moebius function. What is a combinatorial interpretation of the following integer, \begin{align} \prod_{d \mid n} d!^{\,\mu(n/d)}, \end{align} where the product is taken over ...
8
votes
1answer
292 views

A Dirichlet Convolution involving $\mu(n)$ and $\log n$

The following arithmetic identity holds: \begin{align} \Lambda(n) = \sum_{d \mid n} \mu(d) \log \frac{n}{d} \end{align} where $\mu(n)$ is the Moebius function and $\Lambda(n)$ is the von Mangoldt ...
0
votes
2answers
106 views

Counting Spanning Trees with Roots of Unity

In a paper by Kenyon, Propp and Wilson, the number of spanning trees in a certain graph in the hexagonal lattice is: $$ \prod_{a,b,c} (3 - a-b-c)^{1/6}$$ where $a^{3n}=1, (a/b)^n=1,abc=1$ and ...
3
votes
4answers
58 views

How to prove that if $m = 10t+k $ and $67|t - 20k$ then 67|m?

m, t, k are Natural numbers. How can I prove that if $m = 10t+k $ and $67|t - 20k$ then 67|m ?
5
votes
1answer
163 views

P[random x is composite | $2^{x-1}$ mod $x = 1$ ]?

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$ (Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ? How did you calculate this? More info: ...
8
votes
4answers
391 views

Is there a Definite Integral Representation for $n^n$?

The factorial $n!$ has a nice representation as definite integral: $$ n!=\Gamma(n+1)=\int_0^\infty t^{n} e^{-t}\, \mathrm{d}t. \! $$ Is it possible to write down such an integral for $n^n$ as ...
8
votes
1answer
168 views

optimality of 2 in a continued fraction theorem

I'm giving some lectures on continued fractions to high school and college students, and I discussed the standard theorem that, for a real number $\alpha$ and integers $p$ and $q$ with $q \not= 0$, if ...
1
vote
0answers
31 views

Prove that there are at least 50% of numbers $b$ which satisfy ${b_0}^{n-1} \not \equiv {1} \mod{n}$ if one such $b_0$ exists . [duplicate]

Possible Duplicate: Accuracy of Fermat's Little Theorem? $n$ is odd and composite number,and there exists $b_0$ , $0<b_0<n$ such that $gcd(n,b_0)=1$ and ${b_0}^{n-1} \not \equiv ...
1
vote
0answers
97 views

Infinitesimals and infinite elements among the transseries

In the quest for extensions of $\mathbb{R}$ and $\mathbb{C}$ that contains infinitesimals, infinities (and even more exotic beasts like $\omega - 1$ and $\sqrt{\omega}$) I came across the theory of ...
7
votes
3answers
212 views

Generating random numbers with the distribution of the primes

I would like to generate random numbers whose distribution mimics that of the primes. So the number of generated random numbers less than $n$ should grow like $n / \log n$, most intervals ...
2
votes
1answer
613 views

A power-exponential congruence equation

Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$ My thought: ...
30
votes
3answers
511 views

Constructing $\mathbb N$ from the set of factorials

Let S be the set $\{0!, 1!, 2!, \ldots\}$. Is it possible to construct any positive integer using only addition, subtraction and multiplication, and using any element in S at most once? For example: ...
0
votes
1answer
127 views

Determining if sets are nonempty

How to show that these sets are nonempty (here $\mid $ means "divides")? Here N is an arbitrary large integer and q is some fixed integer. $R = \lbrace k \in {\mathbb N}:(kN\mid k!) \wedge ((k - ...
0
votes
1answer
589 views

Multi binomial theorem application

If i have the polynomial expression $(a_1x+b_1y+c_1)^p. (a_2x+a_2y+c_2)^d$, and with assumptions $a_1+b_1<<c_1$ , $a_2+b_2<<c_2$, can i expand this as a product of binomials using the ...
3
votes
1answer
166 views

How many primes $p$ are there such that $2p^{3} + 206$ is a perfect square?

How many primes $p$ are there such that $2p^{3} + 206$ is a perfect square? My approach: Let the square be $k^{2}$, then $$2p^{3} + 206 = k^{2}$$ $$2p^{3}=k^{2} - 206$$ $$2p^{3}=(k+√206)(k-√206)$$ ...
3
votes
3answers
246 views

Prove or disprove $\lim\limits_{n \to \infty} (p_{n+1} - p_{n})/\sqrt{p_n} = 0$

Can anyone prove or disprove the following statement? $$ \lim_{n \to \infty} \frac{p_{n+1} - p_{n}}{\sqrt{p_n}} = 0.$$
2
votes
1answer
143 views

Is there any new improvement in the proof or disproof of the twin prime conjucture?

I think this is not the first question about twin primes here, but my own is the latest one! I am a postgraduate student in Mathematics interested in the field of number theory. While searching on ...
12
votes
1answer
473 views

Updates on Lehmer's Totient Problem

As I read here and in many books on the Theory of Numbers, we are yet to prove or disprove the existence of any composite $n$ such that $\phi(n)\mid n-1$. Is there progress in this line?
2
votes
1answer
186 views

Classical Hecke eigenforms for $\Gamma_0(p)$.

I am in need of classical eigenforms for $\Gamma_0(p)$. In particular I need these to be newforms for each of the even weights 8 to 26 and would settle just for cases $p=2,3$ at this moment in time. ...
6
votes
1answer
941 views

Deciding whether $2^{\sqrt2}$ is irrational/transcendental

Is $2^\sqrt{2}$ irrational? Is it transcendental?
2
votes
0answers
353 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 ...
4
votes
3answers
668 views

Relationship between prime factorizations of $n$ and $n+1$?

Are there any theorems that give us any information about the prime factorization of some integer $n+1$, if we already know the factorization of $n$? Recalling Euclid's famous proof for the infinity ...
1
vote
2answers
142 views

Under which conditions does $a^n \equiv 1\mod(b) \Rightarrow\ a^{n^m} \equiv 1\mod(b) $? Can you prove it?

Under which conditions does $a^n \equiv 1\mod(b) \Rightarrow\ a^{n^m} \equiv 1\mod(b) $? What about viceversa? What is the strongest result(s) that can be proved regarding this kind of thing? I'm ...
2
votes
1answer
158 views

Units in number fields with complex embeddings

Assume that we have an algebraic number field with integers $o$, and with a complex embedding $\iota$. What can be said about the image $\iota( o^\times)$ under $\iota$? Is it discrete? Is ...
4
votes
3answers
432 views

How to prove floor identities?

I'm trying to prove rigorously the following: $\lfloor x/a/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$ for $a,b>1$ So far I haven't gotten far. It's enough to prove this instead ...
4
votes
3answers
322 views

Show that the curve $y^2 = x^3 + 2x^2$ has a double point, and find all rational points

Show that the curve $y^2 = x^3 + 2x^2$ has a double point. Find all rational points on this curve. By implicit differentiation of $x$, $-3x^2 - 4x$ vanishes iff $x = -4/3$ and $0$. By implicit ...
1
vote
1answer
907 views

Solving a polynomial modulo an integer

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
6
votes
1answer
134 views

There are infinitely many $m$ such that $m^4 + 1$ has large prime factors

How do I prove that there is infinite set of numbers $m$ such that the biggest prime divisor of $m^4+1$ is bigger than $2m$?
1
vote
2answers
1k views

prove that $x^2 + y^2 = z^4$ has infinitely many solutions with $(x,y,z)=1$

Prove that $x^2 + y^2 = z^4$ has infinitely many solutions with $(x,y,z)=1$. Do I use the terms $x= r^2 - s^2$, $y = 2rs$, and $z = r^2 + s^2$ to prove this problem? Thanks for any help.
8
votes
1answer
187 views

limit connected with a periodic function

Let $f$ be a $1$-periodic function, i.e., $f(x+1)=f(x)$, defined on the interval $(0, 1)$ by the formula $$ f(x)=2x-1. $$ For a real number $x$ consider the series $$ \sum_{n=1}^\infty\frac{f(nx)}{n}. ...
8
votes
1answer
625 views

What are possibilities to disprove the Collatz Conjecture?

I was thinking about the Collatz Conjecture yesterday, and as opposed to trying to prove it, I was considering what would make the conjecture false. There were only two cases I could think of: We ...
3
votes
2answers
159 views

show that $x^2+y^2=z^5+z$ Has infinitely many relatively prime integral solutions

How to show that this equation: $$x^2+y^2=z^5+z$$ Has infinitely many relatively prime integral solutions
3
votes
1answer
112 views

Minimal $x$ for which $\phi(k) > n$ for all $k > x$

It's well-known that $$ \liminf_n\frac{\varphi(n)\log\log n}{n}=e^{-\gamma} $$ and there exists an effective version $$ \varphi(n)>\frac {n}{e^\gamma\log\log n+\frac{3}{\log\log n}} $$ valid for ...
2
votes
1answer
239 views

How many circular distinct compositions of $n$ into $k$ parts at most $g$

how many circular distinct sequences (e.g. $(4124)\equiv(4412$)) are there that sum up to $n$, have $k$ elements may be non-negative integers at most $g$? In other words: we're looking for the number ...
8
votes
5answers
1k views

How to solve this Pell's equation $x^{2} - 991y^{2} = 1 $

How to solve the following Pell's equation? $$x^{2} - 991y^{2} = 1 $$ where $(x, y)$ are naturals. The answer is $$x = 379,516,400,906,811,930,638,014,896,080$$ $$y = ...
9
votes
6answers
2k views

Sum of the series : $1 + 2+ 4 + 7 + 11 +\cdots$

I got a question which says $$ 1 + \frac {2}{7} + \frac{4}{7^2} + \frac{7}{7^3} + \frac{11}{7^4} + \cdots$$ I got the solution by dividing by $7$ and subtracting it from original sum. Repeated for ...
19
votes
1answer
2k views

A proof of Wolstenholme's theorem

This was inspired by this question. I tried to use the identity $${2n \choose n}=\sum_{k=0}^n {n \choose k}^2$$ (see this question) to prove that $$\binom{2p}p\equiv2\pmod{p^3}$$ if $p\gt3$ is ...
4
votes
1answer
101 views

Integers that are a sum of two $k$th powers in $n$ different ways

Do there exist infinitely many $k$ such that for all $n$ we can find a sequence $x_i$ of distinct natural numbers such that $x_1^k+x_2^k=x_3^k+x_4^k=\cdots=x_{2n-1}^k+x_{2n}^k$ ?
0
votes
2answers
154 views

if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$? I'm aware this has to do with quadratic residues but I do not know how to actually solve it. $p$ is a prime of form $4k+3$