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

Two conjectures regarding $\varphi(n)$

There is a famous unsolved problem called Lehmer's Totient Problem which states that, $\varphi(n)\mid n-1 \implies n$ is a prime. Where $\varphi(n)$ is Euler's Totient Function. I was ...
0
votes
0answers
137 views

Numbers put around a circle

Nine distinct positive integers are arranged in a circle such that the product of any two non-adjacent numbers in the circle is a multiple of n and the product of any two adjacent numbers in the ...
0
votes
0answers
21 views

Number theory related problems of proving r=s in a given condition [closed]

Suppose for some positive integers 'r' & 's', the number 2^r is obtained by permuting the digits of the number 2^s in decimal expansion. Prove that r = s.
2
votes
1answer
19 views

Cyclic congruencies

Suppose $a$ and $b$ are positive integers. Set $x_n := a^n $ modulo $b$. Consider $\{x_n\}$. My question is: is it always true that this sequence must be cyclic? I am guessing there is some ...
3
votes
1answer
27 views

Relatively Prime Numbers and Number of Divisors of n

Find all positive integers $n$ such that $\phi(n) + \tau(n) > n$. I'm not sure how to deal with such abstract functions... help?
12
votes
2answers
633 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
1
vote
2answers
73 views

References for Riemann Hypotheis giving the best bound for Prime Number Theorem

Which books cover the proof that Riemann Hypothesis is equivalent to the best error bound for the Prime Number Theorem? My understanding is that Riemann Hypothesis is equivalent to the best bound of ...
4
votes
1answer
25 views

Lattice basis for prime divisor of $(p)$ [closed]

Suppose that $d \equiv 2$ or $3$ modulo $4$, and that a prime $p \neq 2$ does not remain prime in $R$. Let $a$ be an integers such that $a^2 \equiv d$ modulo $p$. How would I go about showing that ...
2
votes
0answers
34 views

Request for hint: The FLAMES game

The game is the following. Take the word FLAMES. It has 6 letters. Choose a number, say 9. Then strike off the letters in FLAMES by cylcilcally counting in steps of 9 letters. So we get the following ...
1
vote
3answers
57 views

Prove $1+ (\frac{1}{x}) \geq (\frac{1}{x^4}) +(\frac{1}{x^3})$ [closed]

Prove That $$1+ \frac{1}{x} \geq \frac{1}{x^4} + \frac{1}{x^3}$$ where $x \in \mathbb Z^{+}$
4
votes
1answer
86 views

Proper Bernoulli Function Generating Function

Consider the function $$\frac{t}{e^t - 1} = \sum_{i=0}^{\infty}\frac{B_i}{i!}t^i$$ This has been one of the famous generating functions for the bernoulli numbers. What about the function associated ...
-2
votes
0answers
15 views

Where can I find theorems that relate the digits of some integer? [closed]

I'm looking for ways to relate the digits of a positive integer, i.e. $a = a_na_{n-1}...a_2a_1$ For example there is a theorem that states a number $a\in\mathbb{Z}$ is divisible by $3$ iff the sum ...
0
votes
1answer
15 views

$m,n>1$ are relatively prime integers , then are there at-least four idempotent (w.r.t. multiplication) elements in $\mathbb Z_{mn}$ ?

If $m,n>1$ are integers such that $g.c.d.(m,n)=1$ then is it true that there are at-least four elements in $\mathbb Z_{mn}$ such that $x^2=x$ ( i.e. idempotent ) ?
1
vote
0answers
13 views

Proof of Polyates Lemma

In Sbiis Saibian's site I came across Polyates Lemma which states that $$(b \uparrow^k m) \uparrow^k n\ <\ b\uparrow^k (m+n)$$ for all positive integers b,m,n,k with $b\ge 2$ and $k\ge 2$. He ...
0
votes
3answers
44 views

Help explain the end of this proof for infinitely many primes?

by contradiction, assume finitely many primes $p_1, p_2,\cdots, p_k$. let $N = p_1p_2\cdots p_k + 1$. Note $N > 1$. Now, by the fundamental theorem of arithmetic, there exists a number $p_j$, where ...
1
vote
1answer
44 views

$2013!$ ends in a string of zeros. How many of them are there?

$2013!$ ends in a string of zeros. How many of them are there? Work The answer is given like this:(Kindly explain why this is so) $2$’s and $5$’s pair off to produce multiples of 10 and since there ...
0
votes
2answers
36 views

Number of solutions to square root equation

Find the number of distinct pairs of integers $(x, y)$ such that $0 < x < y$ and $\sqrt{1984} = \sqrt{x} + \sqrt{y}.$ I know that $\sqrt{1984}=8\sqrt{31}$, but am not sure how to use it. Could ...
2
votes
1answer
40 views

Diophantin equation $a^3+b^3=c^3+5$

When trying to solve another equation, I came up with this equation: $$a^3 + b^3 = c^3 + 5, \space\space (a,b,c)\in\mathbb{Z}^3$$ It seems that it doesn't have any solutions. I tried to prove this. ...
1
vote
0answers
25 views

Show Equivalence of Binary Quadratic Forms

I've been stuck on these two problems from my problem set for quite a while. Any help would be appreciated! 2)Suppose that $ax^2 + bxy + xy^2$ is equivalent to $Ax^2 + Bxy + Cy^2$. Show that $gcd ...
3
votes
1answer
38 views

Let x and y be two positive real numbers with x<y. Using only the axioms for real numbers, show that 0 < 1/y < 1/x

Let x and y be two positive real numbers with x < y. Using only the axioms for real numbers, show that 0 < 1/y < 1/x I apologize for how it looks, but I'm not very good with formatting. How ...
1
vote
1answer
48 views

Trying to find formula for max number of nodes in a non-Binary tree.

I'm trying to find the max number of nodes in a tree that is defined as follows: The root can have at most $2$ children. Each subtree on the left can have at most $L$ children. Each subtree on the ...
5
votes
0answers
79 views

How important is Differential Geometry for Number Theory?

The title pretty much says it. To elaborate slightly, I am, of course, aware of the huge role played by Algebraic Geometry in Number Theory but I'm not so sure about Differential Geometry. I would be ...
-2
votes
0answers
27 views

Congruence modulo numbers together [closed]

Please, help me solve this equation: $x^{17386} \equiv 43927 \;(\bmod\; 64349)$ Thanks. Regards.
2
votes
1answer
95 views

Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair

Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
0
votes
1answer
38 views

Demostrate that: $ \tau(n)\varphi(n) ≥ n$

Either $n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ the factorization prime of $n>1$. Demostrate: $$ \tau(n)\varphi(n) ≥ n$$ Help me with this excersices, $\tau(n)$ is tao, $\varphi(n)$ is Euler ...
2
votes
2answers
46 views

Diophantine equation $x^2 -y^2 = n$

Is there a method to find how much integer solutions $(x,y)$ has the diophantine equation $$x^2-y^2=n,$$ for a given $n \in \mathbb{Z}$?
1
vote
0answers
34 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
0
votes
2answers
45 views

a question about relatively prime numbers

Is it true that if $m, n$ are relatively prime integers, then $mn$, $m-n$ are also relatively prime? It seems intuitively true but I can't prove it... Could anyone help me how to prove it?
1
vote
0answers
26 views

Is there a formula for n/rad(n)

Are there any known formulas for $n/\mathrm{rad}(n)$; summation or otherwise, that do not involve the Mobius function? Where may I find a list of formulas for this function of any type? Here ...
3
votes
4answers
52 views

What is a counting number?

The definition of natural number is given as The counting numbers {1, 2, 3, ...}, are called natural numbers. They include all the counting numbers i.e. from 1 to infinity. at the link ...
1
vote
1answer
74 views

Generalizing Bertrand's Postulate

Is it possible that for any integer $y \ge 2$, there exists an integer $x$ such that if an integer $n \ge x$, then for all integers $z \le n^y$, there exists a prime $p$ such that $z \le p < z+n$ ...
3
votes
4answers
51 views

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$. Hello. I am working on a review sheet for my test tomorrow and I am stuck on this ...
2
votes
2answers
36 views

Show that $ p^{(q-1)} + q^{(p-1)}$ is congruent to $1 \hspace{1mm } ($mod $ pq)$

Same review sheet, sorry for posting so much. But any help is appreciated. Let $p$ and $q$ be distinct prime numbers. Show that $p^{(q-1)} + q^{(p-1)} \equiv 1 \hspace{1mm } ($mod $pq)$. (hint: ...
2
votes
1answer
57 views

Number of solutions of $3x^2 - 5x + 3\equiv 0 \pmod{m}$?

I'm asked, for each of the following values of $m$, to find the number of solutions (in the set $Z_m$) of the quadratic congruence $3x^2 - 5x + 3\equiv 0 \pmod{m}$. For $m=53$ $m=73$ ...
2
votes
3answers
46 views

$n$ is twice the sum of squares of digits of $n$

Let $f(n)$ denote the sum of squares of digits of $n$, that is $$ f(10k+r) = \begin{cases} r^2 + f(k) &\text{for }10k+r \neq 0,\\ 0&\text{otherwise}. \end{cases} $$ I've found (while ...
1
vote
2answers
56 views

Proving there are infinetly many integer solutions to $ x^2 - 3y^2 = 1 $

I am trying to show that there are infinitely many solutions to the following diophantine equation: $$x^2 - 3y^2 = 1$$ But I don't really know where to start. I hear there are numerical ways to ...
3
votes
2answers
89 views

Find the function of integer numbers $\sum_{n=0}^{\infty }\frac{n^k}{n!}=f(k) \cdot e$

Find the function of integer numbers $$\sum_{n=0}^{\infty }\frac{n^k}{n!}={f(k)}\cdot e$$ I took many values of $k$ and I found the following results $$\sum_{n=0}^{\infty }\frac{n^1}{n!}=e$$ ...
5
votes
1answer
48 views

Lower bound of Euler phi function times sum of divisors

After some work, I got this nice inequality: $$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$ where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm ...
8
votes
2answers
417 views

Let $a=43120$ How many positive divisors does a have?

I am doing a review assignment and I'm stuck on this problem. a) How many positive divisors does $a$ have? I got $60$ b) How many positive integers less than $a$ are relatively prime to $a$? I got ...
0
votes
0answers
22 views

any value to formula for n/rad(n)? [closed]

If I had a simple summation formula using only index of summation $j$ and variable $n$, using only a floor function and it equated to $n/rad(n)$, would it be of any value?
1
vote
0answers
87 views

Counting arrays problem [on hold]

Given N, M and D I need to count how many sequence of N elements a[1],a[2].....a[n] can be formed which satisfy these 2 conditions : Each element is between 1 ≤ Ai ≤ M. Greatest common divisor of ...
1
vote
2answers
26 views

How to find smallest integer which is greater than N positive primes

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula: ...
0
votes
0answers
29 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
11
votes
0answers
201 views
+50

On the problem of polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$

The question titled "Polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$" which was posed on MathOverflow attracted quite a lot of attention (and may be the question with most wrong ...
1
vote
1answer
47 views

What is a counterexample for this one?

Let $x$ be an irrational number. Let $\{a_0\}$ be the sequence of positive integers except for $a_0$ such that $x=a_0+K(1/a_n)$. Let $a,b$ be integers such that $b>0$ and $gcd(a,b)=1$ and ...
2
votes
1answer
76 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 ...
0
votes
1answer
20 views

How to check if a number say 'k' can be formed by adding any number of elements in set/array A?

It is known to me that element 'k' is less than the sum of all elements in the set/array. I know the solution if 'k' can be formed adding any two numbers or three numbers in the set. There are well ...
-1
votes
3answers
77 views

Prove that if $2|(x^2-1)$, then $8|(x^2-1)$.

Prove that if $2\ |\ (x^2-1)$, then $8\ |\ (x^2-1)$.
1
vote
1answer
39 views

Solving $x^n \equiv a \text{ (mod } p)$ in $\mathbb{Z}$

I want to show that for any integers $a$ and $n,$ ($n > 1$) there are infinitely many primes $p$ such that $$x^n \equiv a \text{ (mod } p).$$ When $n$ is odd, I used the fact that if $(a,p)=1$ ...
3
votes
2answers
68 views

Integer inequality: $x + y +z> a + b + c$ does not imply $xyz > abc$

Prove by contradiction that for any integers $x,y,z,a,b,c$ greater than $0$ such that $x+y>a+b$, it is not implied that $x\cdot y\cdot z>a\cdot b\cdot c$? Obviously this statement is true. ...