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

How would you prove $ab|c$ knowing that $a|c$ and $b|c$ and $\gcd(a,b) = 1$? [on hold]

If $a|c$ and $b|c$ and $\gcd(a,b) = 1$, prove that $ab|c$.
2
votes
2answers
11 views

Square Free congruence modulo n

I am trying to show that if $a^n\equiv a\pmod n$ for all integers $a$ that $n$ is square free. I have an idea to start with the contradiction that suppose $n=p^2m$ for some prime $p$, then n does not ...
-3
votes
2answers
27 views

Finding Square Roots

Well, i have a method to find square roots to any number. for Eg To find $\sqrt{58}$ or any number. We have to find which perfect square is place before it. 49 is placed before 58. What we have to do ...
1
vote
2answers
34 views

How I can prove that for any natural number $n$ such that $30<n$, $\pi(4n-3)<n$?

I need to proove that for any natural number $n>30$: $$\pi(4n-3)<n.$$ In this inequality, $\pi(x):\mathbb{N}\to \mathbb{N}$ is the defined as follows: $$\pi(x):=Card(\lbrace p \ | \ p\leq x\ \ ...
0
votes
0answers
2 views

Injectivity of idele norm map

Let $K/F$ be an extension of global fields (I'm considering number fields, but my question may be also considered in function fields). We may define a norm map on the idele groups $$N_{K/F}:\Bbb ...
1
vote
3answers
42 views

For which $n \in \mathbb{N}$ does $x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$ have at least $7$ distinct solutions?

I have to find one $n \in \mathbb{N}$ such that $$x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$$ has at least $7$ distinct solutions in $\mathbb{Z}_n$ (or, equivalently, $f(x) = x^8 + ...
1
vote
1answer
35 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
0
votes
0answers
26 views

How to square a number that got more digits than search results “digits” on Google.

I am implementing the quadratic sieve algorithm. And I got run in unexpected problem. Take a look at those two final steps of the algorithm as described in wiki. Use linear algebra to find a ...
3
votes
1answer
68 views

Product of Primes

Let $\mathbb{P}$ denote the set of prime numbers. How would one evaluate $$\prod_{p\in \mathbb{P}}\frac{p-1}{p}$$ I do not think that the fact that ...
1
vote
1answer
60 views

Show by mathematical induction that the gcd(n,n+1) = 1 for every integer n.

By mathematical induction, how would you show $\gcd(n,n+1)= 1$ for every integer $n$? I'm thinking you would start by knowing that some integer, d, would divide both n and n+1. That's all I have so ...
0
votes
1answer
19 views

Checking if a number is Polygonal

Polygonal numbers are of the form $\cfrac{n^2(s-2)-n(s-4)}{2}$, where $s$ is the number of sides of the polygon and $n$ is to say which one it is (the $n^{th}$ $s$-gonal number) So my question is, ...
5
votes
1answer
83 views

How many solutions are there of the equation $(\cos a)^x+(\sin a)^x=1$, $x \in \mathbb{R}$.

Is there any solution of the equation other than $x=2$? Please help me. Thank you in advance.
2
votes
1answer
32 views

How are the nontrivial zeros of the Riemann zeta function calculated?

The Riemann zeta function, is the function of the complex variable $s$, defined in the half plane $\Re(s)>1$ by the absolutely convergent series $\zeta(s) = \sum_{n} n^{-s}$ and extends to the ...
0
votes
0answers
40 views

Find the Summation of Summation [on hold]

An Array A consisting of N integers .We perform the following operation M times: for i = 2 to N: Ai = Ai + Ai-1 We have to find xth element of the array ...
1
vote
1answer
14 views

Connecting homomorphism in Galois homology using the standard resolution

Let $G$ be a finite group, although this may not be necessary for almost everything that follows. One of the ways of defining Galois homology groups is using the standard resolution for the ...
2
votes
0answers
32 views

Gaussian elimination algorithm performance

I am developing the quadratic sieve algorithm and I reached a new bottle neck: The matrix processing. I been reading quit a lot about this topic and I found many solutions Gaussian elimination: ...
1
vote
2answers
41 views

Uniqueness of log function with relaxed conditions?

Question If: $$f(a) + f(b) = f(ab)$$ $$ f(1) = 0 $$ $$ a<b \implies f(a) < f(b) \forall a,b \in N $$ where $N$ is the set of natural numbers. Prove or disprove $f$ must be the $\log$ ...
-1
votes
5answers
73 views

Is it accurate to say that multiplication of two integers yields an integer?

I am reading a book in discrete mathematics and it assumes that a multiplication of two integers yields an integer. Although that this book's saying is justifiable since the book is making an ...
0
votes
2answers
16 views

Showing Modulo Congruence Amongst Prime Divisors (Number Theory)

I'm having trouble figuring out how to show the general existence part of the following problem. Suppose $n\in\{1,2,3...\}$ and $n\equiv 7\mod{10}$. Show that $\exists$ a prime divisor $p$ of $n$ ...
1
vote
0answers
37 views

Important numerator and denominators in the evaluation of the integral: $\int_0^\infty x^t \operatorname{csch} x\text{ d}x$

$$\int_0^\infty x^t\operatorname{csch}x\text{ d}x=\frac{a\zeta(t+1)}{b}$$ for $t\in\Bbb{N}$ How might one represent $a,b$ in terms of $t$? (Note that $a,b\in \Bbb{N}$) If possible, could one also ...
2
votes
1answer
20 views

Modular Arithmetic and Greatest Common Divisor.

In my algebraic structures textbook I have come across a tricky question that I am trying to solve which goes as follows: suppose that $d|(a^n-1) $ and $d|(a^m-1)$ where $m,n$ are natural numbers ...
0
votes
1answer
32 views

Find all the numbers $a$ such that the number $an(n+2)(n+4)$ is an integer for all $n \in \mathbb{N}$

Find all the numbers $a$ such that the number $an(n+2)(n+4)$ is an integer for all $n \in \mathbb{N}$ It's trivial to see that if $a$ is irrational, we get no solution. Thus $a \in \mathbb{Q} ...
29
votes
5answers
2k views

$-1$ as the only negative prime.

I was recently thinking about prime numbers, and at the time I didn't know that they had to be greater than $1$. This got me thinking about negative prime numbers though, and I soon realized that, for ...
0
votes
0answers
37 views

on the least primitive root of a prime

There is an article on the least of primitive root of a prime in this link On the second page you will see ...
2
votes
1answer
51 views

Homeomorphism between $\mathbb{R}$ and $\mathbb{Q}$ - why does cardinality matter?

When I look up why $\mathbb{R}$ and $\mathbb{Q}$ are not homeomorphic, almost all the answers just say something along the line of "Because, Cardinality" and then ends there. Can someone provides ...
0
votes
2answers
37 views

Intersection of dense sets in $\mathbb{N}$

Let's call $A\subseteq\mathbb{N}$ dense if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} = 1.$$ Is the intersection of two dense sets dense again? Or does the intersection of two dense ...
2
votes
1answer
32 views

What is the significance of Coleman maps arising in Iwasawa thoery?

I have come across two instances of "Coleman map" Let $E$ be an elliptic curve defined over $\mathbb{Q}_p$. Let $k_\infty$ be the unique $\mathbb{Z}_p$ extension of $\mathbb{Q}_p$ contained in ...
0
votes
0answers
27 views

Is there an arbitrarily large set of naturals so that the sum of each two has exactly $n$ prime divisors? What about an infinite set? [on hold]

Is there an arbitrarily large set of naturals so that the sum of each $2$ has exactly $n$ prime divisors where $n$ is fixed? What about an infinite set? For $n=1$ this is clearly false, what ...
1
vote
0answers
12 views

Best pattern of cinnamonbuns on a baking tray?

Imagine that i have a 50 x 100 cm baking tray, and i have a load of cinnamonbuns, shaped like a circle with a diameter of 10cm. How do i calculate the best place to place my cinnamonbuns, as the ...
1
vote
0answers
18 views

Stern-Brocot Tree and sum of coefficients of continued fraction

Suppose we are given a continued fraction $$\frac{p}{q}=a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\frac{1}{a_{4}+\cdots}}}$$ I am trying to find an expression, possibly asymptotic, for the sum of the ...
0
votes
0answers
25 views

Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$.

Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...
2
votes
2answers
40 views

Given integers $x,\,y$ s.t. $x^2-16=y^3$, show that $x+4$ and $x-4$ are perfect cubes

Suppose $x$ and $y$ are some integers satisfying $$x^2-16=y^3.$$ I'm trying to show that $x+4$ and $x-4$ are both perfect cubes. I know that the greatest common divisor of $x+4$ and $x-4$ must divide ...
1
vote
0answers
20 views

How can we prove a statement is provable?

Given a concrete mathematical statement, such as BSD conjecture(https://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture), do we know if it is provable?
1
vote
1answer
56 views

An odd property of Egyptian fractions

This question arose through a response to [this post] Is there any partial sums of harmonic series that is integer? For which integers $N>1$ does the fraction $\frac 1N$ appear in the Egyptian ...
1
vote
0answers
23 views

square monotonic numbers

A monotonic number is a number in which the digits are in non-decreasing order. I found by computer that most of these numbers are squares of these numbers $$3 \ldots 34,3 \ldots 35,3 \ldots 37,3 ...
-7
votes
0answers
44 views

Why are there twin primes? [on hold]

Speculation encouraged. Isn't it strange that there are probably infinitely many despite the size of the numbers? Why is that?
1
vote
2answers
62 views

How can Mersenne Prime rule be valid if $2047$ isn't prime?

The rule of Mersenne Prime says that $2^p - 1$ is prime if $p$ is prime. $2^{11} - 1 = 2047$ satisfies the condition, but it's not a prime as it can be divided by two prime numbers $23$ and $89$. ...
3
votes
4answers
87 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
0
votes
1answer
19 views

Connected Components of p-adic rationals

Notation: $p$ - a prime integer, $\Bbb{Z}_p$ - set of $p$-adic integers, $\Bbb{Q}_p$ - set of $p$-adic rationals, $\Bbb{Q}$ - set of rationals, $\Bbb{R}$ - set of reals. While reading up on ...
0
votes
0answers
20 views

Prime division algebra level 5

Let $P$ be the number of integers $n$  for which $n^4-52n^2+595$ is prime, and let $D$ be the number of distinct primes that can be represented in this form. Find $P+D$.
1
vote
0answers
22 views
+300

$n^a$ integral for all integer $n$ implies $a$ integral

Let $a>0$ be a real number, such that for all integers $n\geq 1$: $n^a \in \mathbb N$ Show that $a$ must be an integer. It's not difficult to show this when $a$ is a rational number: ...
2
votes
0answers
19 views

Finite amount of consecutive smooth numbers

is there a short proof of the fact that there is a finite amount of consecutive smooth numbers (meaning Given a finite set B, there is a finite amount of pairs $n,n+1$ so that both can be expressed as ...
0
votes
0answers
16 views

What are some easy to prove results on the density of primes?

Bertrand's postulate states that for any integer $n>3$, there's always a prime $p$ between $n$ and $2n-2$. That result sets a reasonable 'lower bound' on how often we can expect primes to show up, ...
0
votes
0answers
17 views

An upper bound for the Chebyshev function?

The Chebyshev functions are defined as $\psi(x) = \sum_{p^m \leq x} \log n$ and $\theta(x) = \sum_{p\leq x} \log p$, where $p$ is a prime, $m\geq 1$ is an integer and $n=p^m$ in $\psi(x)$. It is known ...
-3
votes
0answers
30 views

number based problem [on hold]

You have two numbers which is "444444......4"(2016 4's) & "88888.....89"(2015 8's). Now add the two numbers then calculate the root.then calculate the sum of the digits of root.
0
votes
2answers
39 views

Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
1
vote
1answer
12 views

order of a subrgoup of rank $r\geq 2$ in $\mathbb{F}_p^*$

Let $a,b\in \mathbb{F}_p^*$ with orders $o_p(a)=|\langle a \rangle|=\alpha$ and $o_p(b)=|\langle b \rangle|=\beta$. I have few questions: 1) Is it true in this case ($\mathbb{F}_p^*$ cyclic) that ...
0
votes
0answers
27 views

Is the absolute value of the intersection of two functions related to the nontrivial zeros always equal to $\sqrt{2}$?

With $\displaystyle \chi(s)=\pi^{-\frac{s}{2}}\,\Gamma\left(\frac{s}{2}\right)$ and $K(s)=\Psi\left(\frac{s}{2}\right)-\ln(\pi)$, with $\Psi\left(s\right)$ the digamma function, then the Riemann ...
0
votes
5answers
55 views

How can I prove that $\frac{21n -3}{4}$ and $\frac{15n+2}{4}$ are never both integers?

I have converted this to a problem of modular arithmetic. I seek to prove that $21n-3$ and $15n+2$ are never congruent to $0\pmod 4$ for the same value of $n$. I observed that $21n$ is ...
0
votes
0answers
22 views

How can I define $H+K$? [duplicate]

Let be integers 5 and 100, and let be $H=5Z$ and $K=100Z$ subgroups of the additive group $Z$. How can I define the subgroup $H+K$ ? I think $5Z+100Z=5Z$ because mcd(100,5)=5 but I'm not sure that ...