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

For an odd prime $p$, $\;p =1 \pmod 4,\; \;x^2+1 = 0 \pmod p$

$$\text{ If } p \neq 2 \text{ is a prime, we know that: }$$ $$\left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$$ According to this,prove that: $$p \equiv 1 \pmod 4 ...
1
vote
1answer
82 views

If p and q are distinct prime numbers, it is true that we always have $p^{q-1}+q^{p-1} \equiv 1 \mod pq$?

If p and q are distinct prime numbers, it is true that we always have $p^{q-1}+q^{p-1} \equiv 1 \mod pq$? More generally if $m,n \in \mathbb{N}$ are relatively prime, is it true that ...
1
vote
1answer
28 views

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that If the equation has a solution, then $(\frac{Q}{P})=1$ That the coverse ...
1
vote
1answer
109 views

Problem from Apostol's analytic number theory book

Im trying to solve the exercise 13.2 in Apostol's analytic number theory book: Let $A(x)=\sum_{n\leq x}a(n)$, where $a(n)$ is zero unless $n=p^k$ for some prime $p$, in that case $a(n)=1/k$. Prove ...
1
vote
1answer
58 views

Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor ...
1
vote
1answer
72 views

A question about squares

The numbers from 1 to $ 2013^2 $ are written row by row into a table consisting of $ 2013 \times 2013 $ cells. Afterwards, all columns and all rows containing at least one of the perfect squares $ 1, ...
1
vote
1answer
91 views

Prove that in any base the number of digits composing the repetitive mantissa of the reciprocal of a prime $p$ never exceeds $p-1$.

I was trying to find bases where the reciprocals of primes have a short repetitive mantissa. Here is what I found: http://imagizer.imageshack.us/a/img835/7738/c7gb.png The bases are on the left. The ...
1
vote
1answer
94 views

Prove or disprove that $\forall k\in\mathbb N$ there exist tree consecutive primes such that $p_i-p_{i-1}\gt k$ and $p_{i+1}-p_{i}\gt k$

Prove or disprove that for every positive integer $k$, there exist tree consecutive primes $p_{i-1}, p_i, p_{i+1}$ such that $p_i-p_{i-1}\gt k$ and $p_{i+1}-p_{i}\gt k$. It's well known that ...
1
vote
3answers
67 views

Prove that $(n\mid m$ and $m\mid n) \iff (n=m)$

Prove that $(n\mid m\text{ and }m\mid n) \iff (n=m)$. $\rightarrow$ $n\mid m$ and $m\mid n \rightarrow m=an$ and $n=bm \rightarrow a \geq 1$ and $b \geq 1 \rightarrow m=n$. $\leftarrow$ How do I ...
1
vote
1answer
109 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
1
vote
2answers
71 views

MATLAB Newton non-linear equation

I have the following non-linear equation: where $w0=0.25,w0=0.5,w0=0.75$. I have to prove that if $k$ is a root, then also $−k$ is a root and that there exists only one $k∈(0,1)$ root, but my ...
1
vote
1answer
34 views

Finding the Best Constant in Prime Counting Function Relation

How close can we approximate the best constant $c$ such that $n^{\pi(2n)- \pi(n)} \le c^n$ for all positive integers $n$. I know that $c = 4$ works from $n^{\pi(2n)-\pi(n)} < \prod_{n < p \le ...
1
vote
1answer
59 views

Number of solutions modulo $p^2$

I am asked to do the following: Let $p$ be a prime number, suppose that $d|p-1$, investigate the number of solutions to the equations $$x^d\equiv 1 \mod p$$ and $$x^d\equiv 1 \mod p^2$$ ...
1
vote
1answer
78 views

$m^k-k^m=17$ find solutions.

Find all solution to the equation $m^k-k^m=17$ where $m,k\ge 2$ and are positive integers. I have analysed the equation by $mod(3) $ but I didn't get anything.
1
vote
2answers
40 views

Power of prime number in $n!$ - prove this formula

How to prove: for $ l := \max\{i \in \mathbb{N}_0 : p^i \mid n!\} $ it holds: a) $l = \sum_{i=1}^\infty [\frac{n}{p^i}]$ b) $l \leq [ \frac{n}{p-1} ]$ ? If I take a closer look at the sum in a) I ...
1
vote
1answer
60 views

Greatest common divisor expression

How can we show that for a fixed positive integer $a$ $a^2+\left[\text{GCD}(a,b)\right]^2\equiv0\mod b\,\text{GCD}(a,b)$ has a positive and even number of solutions $b$ (also positive integers)?
1
vote
1answer
82 views

What is known about the ramification index of ramified primes in an arbitrary cyclotomic extension of $\mathbb{Q}$

Let $\zeta$ be a primitive $m$th root of unity, and $L = \mathbb{Q}(\zeta)$. Then $B = \mathbb{Z}[\zeta]$ is the integral closure of $\mathbb{Z}$ in $L$. If $P$ is a prime ideal of $B$ and ...
1
vote
2answers
390 views

Shortest path between three nodes in a graph

I know Dijkstra's algorithm to find the shortest way between 2 nodes, but is there a way to find the shortest path between 3 nodes among $n$ nodes? Here are the details: I have $n$ nodes, some of ...
1
vote
1answer
56 views

Changing order of summation with Möbius function

Let $\mu(d)$ be the Möbius function, and $\mu_r(d)$ be the modified Möbius function which satisfies $\mu_r(d)=0$ if $d$ has strictly more than $r$ distinct prime factors. Let $\psi_r(n)=\sum_{d\mid ...
1
vote
3answers
87 views

Diophantine equation. Three.

Diophantine equation. $X^2+Y^2=qZ^3$ I wonder at what values ​​of the coefficient $q$ equation has a solution. And of course I wonder how she looks like a formula describing their solutions. For ...
1
vote
1answer
65 views

Find $b-d$ when $\log_ab={3\over2}$ and $\log_cd={5\over4}$

$a,b,c$ are three natural numbers such that $\log_ab={3\over2}$ and $\log_cd={5\over4}$. Given: $a-c=9$ Find $b-d$
1
vote
1answer
238 views

Is Douglas Hofstadter's version of Godel's proof utter nonsense?

Is Douglas Hofstadter's version of Godel's proof, which he offers in his book Godel, Escher, Bach, utter nonsense? Hofstadter goes to great length to disguise the fact that there are two distinct ...
1
vote
2answers
99 views

Looking for references

I am looking for reference on the following problem. Let $S= \{ ax_1+bx_2 \mid x_1 \in X_1 , x_2 \in X_2, \}$ where $X_1,X_2\subseteq \mathbb{R}^n$ and $a,b \in \mathbb{R}$. Note that $a$ and $b$ ...
1
vote
3answers
96 views

integer solutions to $x^2+y^2+z^2+t^2 = w^2$

Is there a way to find all integer primitive solutions to the equation $x^2+y^2+z^2+t^2 = w^2$? i.e., is there a parametrization which covers all the possible solutions?
1
vote
1answer
62 views

Asymptotic result about analytic number theory

I don't know if there is any done work done about ehis matter, and I don't have access to research news. I'm interested in this question (I haen't tried to answer it myself, but it seems very ...
1
vote
1answer
84 views

Equation with a sum for the prime-counting function involving the Mobius function

I have come across the statement that $$ \sum_{n\leq x}\sum_{d\mid(n,P_z)}\mu(d) = \sum_{d\mid P_z}\mu(d) \left[\frac{x}{d}\right], $$ where $P_z=\prod_{p\leq z}p$ where $p$ is prime, $\mu(d)$ is the ...
1
vote
1answer
54 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
1
vote
1answer
52 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
1
vote
1answer
41 views

Prove that for $n\ge 2$, the n-th Lucas number is equal to $[a^n+1/2]$

Prove that for n greater than or equal to 2 the n-th Lucas number is equal to $[a^n+1/2]$. The brackets are the greatest integer function, $a = \frac{1+\sqrt5}{2}$. I get every kind of proof we ...
1
vote
1answer
423 views

Show that every nonzero integer has balanced ternary expansion?

show that every nonzero integer can be uniquely represented in the form $e_k3^k + e_{k-1}3^{k-1}+ … + e_13+e_0$ where $e_j= -1, 0, 1$ for $j = 0,1,2,…k$ and $e_k \neq 0$
1
vote
1answer
82 views

If Cramér's is proved?

Harald Cramér proved that under this assumption that the Riemann hypothesis is true., the gap $g_n$ satisfies $$g_n = O(\sqrt{p_n} \ln p_n) ,$$ using the big O notation. Later, he conjectured that ...
1
vote
1answer
78 views

How to show that $\mathbb{Q}_p^*$ is totally disconnected?

Let $\mathbb{Q}_p$ be the field of p-adic numbers and $\mathbb{Q}_p^*$ the set of invertible elements in $\mathbb{Q}_p$. How to show that $\mathbb{Q}_p^*$ is totally disconnected? Thank you very ...
1
vote
2answers
28 views

prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$

Prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$ I did this by contradiction: let $d=(k,m,n)$ so that $d\neq 1$; by definition of greatest common divisor $d|k, d|m, d|n$ ...
1
vote
3answers
395 views

Determine the last two digits of $3^{3^{100}}$

Determine the last two digits of $3^{3^{100}}$ This is one of the problems in the past exam my modern algebra course. I think I need to use euler-fermat theorem but can't figure out how to use it for ...
1
vote
2answers
78 views

What is the time to create a complement of a graph?

It seems to me that the running time to make a complement of a graph with $n$ nodes is $n!$. Is there any way to make this running time polynomial? That is, is there any method to construct a ...
1
vote
2answers
98 views

Given a congruence equation ax = b (mod n), how can I prove this GCD?

I am given the equation $ax = b (mod$ $n)$ and that $d = (a,n)$. Suppose that $x_o$ is a solution to the equation. I need to prove that d is the greatest common divisor of not only a and n, but b as ...
1
vote
2answers
35 views

Can someone help me solve this system of congruences?

I'm a little new to congruences but I think I have it right. I started with the following congruences: $19x \equiv 5 \pmod{2}$ $19x \equiv 5 \pmod{3}$ $19x \equiv 5 \pmod{5}$ $19x \equiv 5 ...
1
vote
1answer
173 views

Pythagorean triples,consecutive terms of an arithmetic progression

I am looking at the exercise: Find all the positive Pythagorean triples that are consecutive terms of an arithmetic progression. $$$$ So,according to the solution that I saw in my notes,we want to ...
1
vote
3answers
691 views

The least number which leaves remainders 2, 3, 4, 5 and 6 on dividing by 3, 4, 5, 6 and 7 is

Problem - The least number which leaves remainders 2, 3, 4, 5 and 6 on dividing by 3, 4, 5, 6 and 7 is? Solution - Here 3-2 = 1, 4-3 = 1, 5-4 = 1 and so on. So required number is (LCM of 3, 4, 5, 6, ...
1
vote
1answer
30 views

Is $n=2$ the only root of $M(n!)$…?

Wolfram can help till $n=9$, but are there other value larger than $2$ for which $$ M(n!)=0, $$ where $M(n)$ is Merten's function.
1
vote
4answers
3k views

What is the remainder when 4 to the power 1000 is divided by 7

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand - Solution - To find the ...
1
vote
1answer
55 views

Convert a Number to a Sentence [closed]

My task is to take any number, and have it replaced with a sentence/string representing its value. To be exact, I want something along the lines of; 150 = hi 151 = hj 152 = hk This of course ...
1
vote
4answers
114 views

The solutions to $x^2+5=y^2$.

Consider the equation $$x^2+5=y^2.\tag{1}$$ If $x,y\in\mathbb{Z}$, what are solutions to (1)? If $x,y\in\mathbb{Q}$, what are solutions to (1)? Note: $\mathbb{Z}$ is the set of all integers and ...
1
vote
2answers
72 views

number theory of coefficients in an infinite sequence of polynomials

EDIT: equivalent formulation by Hurkyl in comments: if $n$ is odd and $p^\nu \parallel n$ and $n > 2k,$ then $$ p^{(\nu + 2 + 2 k - n)} \; | \; \sum_j \left( \begin{array}{c} n \\ 2j \end{array} ...
1
vote
1answer
81 views

Bounds for $(10 \uparrow \uparrow 257) \uparrow \uparrow \uparrow (10 \uparrow \uparrow 257)$

A lower bound of 2[6] (Steinhaus-Moser-Notation) is $$ M:= (10 \uparrow \uparrow 257) \uparrow \uparrow \uparrow (10 \uparrow \uparrow 257)$$ I would like to bound M in the following way : $$10 ...
1
vote
2answers
64 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...
1
vote
2answers
64 views

Let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove $r \mid \phi(n)$.

Let $a \in \mathbb {Z}$, $n > 1$ a natural number with $\gcd(a, n) = 1$, and let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove that $r \mid \phi(n)$. Euler's ...
1
vote
2answers
57 views

How do I prove divisibility by 3 without induction?

How do I prove that: $3$ divides $4^n-1$, where $n$ is a natural number, and $3$ divides $n^3-n$, where $n$ is a natural number? All without induction?(only number theory) Thanks !
1
vote
1answer
81 views

$n^x$, $x$ is irrational number what is the result? [duplicate]

if for a real number $n$ , $n^x$ where $x$ is an irrational number. What is nature of number $n^x$ ? Possible values or how to determine nature of number $n^x$ ? value of square root of 2 rays to ...
1
vote
1answer
69 views

Finding infinite sequences with pairwise relatively prime outputs.

I am looking for a formula which for every element in $\mathbb{Z}$ as an input, gives pairwise relatively prime outputs. That is for example thanks to Greg Martin's suggestion the positive outputs of ...