Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [number-theory]

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.

0
votes
1answer
10 views

Exhibit a reduced residue system mod 7 composed entirely of powers of 3

By trial, I configured that $3,3^2,3^3,3^4,3^5,3^6$ is a reduced residue system composed entirely of powers of $3$. However, why this is happening? Is it true for all relatively prime numbers, though?
-1
votes
0answers
14 views

P*(100!)^k=(10000!) Find max value of k

If p*(100!)^k = (10000!) Find the maximum possible value of k. p is an integer How do I proceed??
1
vote
2answers
34 views

Intro to Classical Number Theory

I am having trouble understanding page 53, of A Classical Introduction to Modern Number Theory, by Kenneth Ireland and Michael Rosen. Corollary 3. $$(-1)^{(p-1)/2} = \left(\frac{-1}{p}\right)$$ ...
-2
votes
2answers
25 views

If $(b,c) = 1$, then $(a,bc) = (a,b)(a,c)$

I do not know how to solve the following: Show that If $(b,c) = 1$, then $(a,bc) = (a,b)(a,c)$ Thanks.
2
votes
2answers
36 views

Analogous results to Euler's theorem

Fermat's little theorem and its generalization, Euler's theorem holds for pair of relatively prime integers. Are there any analogous results for not relatively prime integers ? Thanks in advance.
1
vote
2answers
31 views

are there any elementary formula of $r'_3(n)$?

It is known that every positive integer can be written as sum of three squares if and only if the number cannot be expressed as $4^n(8k+7)$ for any non negative integers $n$, $k$ (Legendre's three ...
0
votes
0answers
24 views

existence of a prime as close as possible to $\sqrt[3]{n}$, for $n$ large enough

I'm studying the property of some extremal graphs in Graph Theory, and in an old paper (1966) I encountered a number theory theorem, that goes as follow : For any $\varepsilon \in ]0,1[$, there exist ...
0
votes
0answers
13 views

Congruences implied by division.

Suppose $a$ is a number of the form $8k\pm3$ (for example) and also suppose that there is some odd prime $p>3$ dividing $a$. Claim: At least some $p|a$ has the property $p=8n\pm3$ for some $n\in\...
0
votes
2answers
35 views

Generators/primitive roots/primitive elements of Prime fields

Algebra by Michael Artin Exer 3.1.7 (Actually Exer 7 of Ch3.2) By finding primitive elements, verify that the multiplicative group $\mathbb F_p^{\times}$ is cyclic for all primes $p < 20$. ...
0
votes
1answer
24 views

Base 5 help! determine if the solution is correct or incorrect

Okay so the question is : Below is a solution for rewriting/representing 321(five) in a different way. Determine if the solution is correct or incorrect and why (by relating it to the original number)...
1
vote
2answers
48 views

Find the natural numbers such that a number is a prime number. [on hold]

Find the natural numbers $x$, $n$ such that $p = x^4+2^{4n+2}$ is prime number.
5
votes
2answers
55 views

Is $\frac{\left(1+\sqrt{4n^2+1}\right)^n+\left(1-\sqrt{4n^2+1}\right)^n}{2^n}$ always an integer?

Let $$a_n = \frac{\left(1+\sqrt{4n^2+1}\right)^n+\left(1-\sqrt{4n^2+1}\right)^n}{2^n}=2^{1-n} \sum _{k=0}^{\lfloor n/2\rfloor} \binom{n}{2 k} \left(4 n^2+1\right)^k,$$ then we have $$a_1=1,\quad a_2=9,...
0
votes
1answer
30 views

Let $p$ be a prime number and consider the set of numbers $S = {1, 2, . . . , p − 1}$. Let $a ∈ S$. Prove the following two claims.

(a) Prove that no two numbers from the list are congruent modulo $p$ 1$·$a, 2$·$a, 3$·$a, ... $(p-2)·a$, $(p-1)·a$ I think I am suppose to assume there exist two number $(x,y)$ that are congruent ...
1
vote
0answers
26 views

Equal polynomials of equal degree at equal x must have equal coefficients?

does anyone know if the following is true? I'm looking at something like $$2^{s_1+s_2+\Delta_2}+2^{s_2+\Delta_2}3-2^{s_1}3^2=2^{s_1+s_2+\Delta_1}+2^{s_2}3-2^{s_1+\Delta_1}3^2$$ And what I notice is ...
2
votes
0answers
74 views

What is the probability that $\gcd(a,b)$ is prime or twice a prime?

Let $a,b \in \mathbb{N}-\{0\}$. Denote the set of prime numbers by $P$. Here it is mentioned that the probability that $\gcd(a,b)=1$ tends to $\frac{6}{\pi^2}=0.60792 \ldots$ What is the ...
0
votes
3answers
44 views

How to prove “Unit digit of a square number”?

How can I prove that the unit digit of a perfect square is always $0,1,4,9,5,6$ and never $2,3,7,8$? It's pretty intuitive but I am having difficulties proving this statement. I had used trial ...
0
votes
0answers
31 views

Why can't this infinite sum be natural?

$$f(k,s)=\sum_{n=1}^{\infty}\sum_{i=1}^k\frac{3^{kn-i}}{2^{ns_k-s_{i-1}}}$$ where $s$ is a set of $k$-length and consists of ascending positive integers. Is there a way to argue that $f(k,s)$ can ...
0
votes
0answers
18 views

about set containment of valuation ring [on hold]

Given that $ u = \frac{a}{b} $ show that {$p \in \mathbb{Z}$ prime such that $v(u) \neq 0$} $\subsetneq$ {primes in factorization of a,b}. $v(u)$ is valuation over Q and we know that it is if $ u=p^...
1
vote
1answer
27 views

continued fraction development of the numbers of the following form, $\sqrt{n^2-1}$

Determine the continued fraction development of the numbers of the following form, $\sqrt{n^2-1}$, with $n>1$ an integer. I wasn't sure how to tackle this, so I just tried to write it out and ...
7
votes
1answer
114 views

Is it true that the number is divisible by $p$?

Question: Let $a, b, c$ be positive integers and $p>3$ be a prime ($ a$ isn't divisible by $p$). Consider a quadratic polynomial $P(x) = ax^2+bx+c$, and assume that there exists $2 p-1$ ...
0
votes
1answer
24 views

Solve quadratic congruence equation by completing square

Q: Solve the congruence $x^2+x+7\equiv 0$ (mod $27$) by using the method of completing the square from elementary algebra, thus $4x^2+4x+28=(2x+1)^2+27$. Solve this congruence (mod $81$) by the same ...
1
vote
0answers
37 views

Is it true that $(2k+1)(2^{4k+1}+(2k-1)^{4k+1})=a^2+(4k+1)b^2$ has no positive integer solution?

Is it true that the equation $$(2k+1)(2^{4k+1}+(2k-1)^{4k+1})=a^2+(4k+1)b^2$$ has no positive integer solution ? Let $A=(2^{4k+1}+(2k-1)^{4k+1})/(2k+1)$, if $q$ is a prime factor of $A$ such that $x^...
0
votes
0answers
12 views

Affine Cipher, find the cipher function and the plaintext

I was checking the following Affine Cipher / modular aritmethic exercise: You intercept a ciphertext $YFWD$, which was ciphered using an affine cipher. You know that the plaintext starts in $ST$, ...
0
votes
0answers
34 views

Is there an option to handle Neumann-series when it diverges? (using infinite-sized Carleman matrices)

Motivation I'm considering functions, represented by Carleman matrices of infinite size, for instance $f(x)=t^x - 1$. Let us denote the iterates of $f(x)$ by indexes on $x$ like $x_0=x$, $x_1=f(x)$, $...
0
votes
0answers
34 views

Question on the difference between harmonic series.

I found the following identity: For $r>s>0$ and integers. \begin{align} \sum_{m=1}^{\infty} \frac{1}{m+r} \frac{1}{m+s} = \frac{H_r-H_s}{r-s} = \frac{1}{r-s} \left( \frac{1}{s+1} + \frac{1}{s+2}...
2
votes
1answer
67 views

Given $a, b$ coprime integers, show that any factor of $a^2 - 2b^2$ is of the form $c^2 - 2d^2$

This is an exercise from Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I imagine the relevant ring here is $Z[\sqrt{2}]$, i.e., we can factor $a^2 - 2b^2$ into $(a + b\...
2
votes
0answers
27 views

Prime counting function $\phi(x)-c(x)$ vs. $x/\ln(x)$

So $\pi(x)$ is the prime counting function. That is to say, it counts the number of primes below a given integer $x$. This function is very important in number theory. I was wondering how well the ...
-1
votes
0answers
23 views

Question on Groups/Number Theory [on hold]

I have a Set R(real numbers) with the following defined binary operation. x*y = ax+by+x and I have to Find a, b, c such that (R, *) is an abelian group. How would I approach this exercise?
1
vote
2answers
29 views

Euclidean GCD calculation and mod

Calculate $6/87 \pmod{137}$ I do not understand the Euclidean GCD algorithm. If someone can please explain the overall logic of this it would be much appreciated.I have posted what the solution is ...
0
votes
2answers
20 views

Groups/Rings/Fields question on Elementary Number Theory

So I understand that for a set to be a GROUP, it must follow certain properties(closure, association etc.). But what I don't get is how do I know during validation of these properties if i must use ...
2
votes
0answers
31 views

Estimation of the last digit of $\frac{\sqrt{m!+1}-1}{10}$

$\frac{\sqrt{m!+1}-1}{10}$ Can you write a formula to work out the numbers surrounding the decimal point? For example when $m=11$ it equals $631.6974438...$ so it would be $1.6$
0
votes
0answers
17 views

Relationship between the finite product of numbers and sum [on hold]

Let's take finite $\{x_1, x_2, ..., x_n\}$ real numbers. Let us define finite sum of $x_i^2$ :$S=\sum_{i=1}^n (x_{i})^2$ and finite product of $x_i^2$ :$P=\prod_{i=1}^{n} (x_{i})^2$? Which one is ...
8
votes
1answer
60 views

Is it consistent with ZF that there is no uncountable set of algebraically independent reals?

Exactly what the title asks. This question was inspired by this one which looks for a countable such set. It is fairly easy to construct a size $\mathfrak{c}$ algebraically independent set of reals ...
0
votes
1answer
56 views

$n$ or $2n$ is a sum of three squares

For a given positive integer $n$, show that $n$ or $2n$ is a sum of three squares. My attempt: If $n$ is a sum of three squares, there is nothing to prove. So assume $n$ is not a sum of three squares....
2
votes
1answer
70 views

Prove that $\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$

I want to prove the following: $$\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$$$\ \text{i.e. } (2x)^2\equiv-3 \pmod p$ where $p$ is ...
2
votes
1answer
74 views

if $d|n$, then $S_2(d) \leq S_2(n)$?

For every positive integer $n$, denote $S_2(n)$ the sum of digits of $n$ in binary form (for example, $S_2(42) =S_2(101010_2)=3$ Is it true that if $(2^k-1)|n$, then $S_2(2^k-1) \leq S_2(n)$ ? If ...
3
votes
5answers
569 views

Are there infinitely-many numbers that are both square and triangular?

I just started to read "Friendly Introduction to Number Theory" but I am getting stuck in the first exercises. 1.1. The first two numbers that are both squares and triangles are 1 and 36. Find the ...
2
votes
1answer
48 views

Prove there are infinitely many positive whole numbers that are NOT of the form $4xy+3x+y$ or $4xy+3x-y$

Problem: Prove that there are infinitely many positive integer numbers that can't be written as $4xy+3x+y$ OR $4xy+3x-y$, where $x,y$ are positive integers, and $y$ can be zero, too. I tried ...
2
votes
1answer
39 views

how can I prove that $p=7,n=2$ is the only solution (sum of divisors)?

Question: Find every pair of $(n,p)$ in which $n$ is a positive integer and $p$ is an odd prime number so that the sum of every positive divisor of $p^{2^n-1}$ is a square number. It can be seen that ...
0
votes
1answer
33 views

Three runners start at different speeds, two at 7:00am, one a 7:01am

Three runners called them Tom, Dick and Harry run along a circular route. Tom takes 5 minutes to complete a round, Dick takes 7 minutes, and Harry takes 11 minutes. Tom and Harry start their run at 7:...
2
votes
2answers
74 views

$m+n+p-1=2\sqrt{mnp}$ in positive integers

If $m,n,p \in N$ and $m+n+p-1=2\sqrt{mnp}$, prove that at least one of $m,n,p$ is a perfect square. There is a duplicate here: Perfect square : $ m+n+p-2\sqrt{mnp}=1$, but I am very confused. Now I ...
3
votes
0answers
51 views

Modularity and the most general $(p, q, r)$ case in the BeChDaYa paper.

In the Bennet, Chen, Dahmen, Yazdani paper, Generalized Fermat equations: A miscellany, on page 24 in section 6 entitled "Future Work", they say: "A limitation of the modular method at present is ...
-2
votes
1answer
59 views

infinite sum can't be natural

Take the following sum. $$f(k,p)=\frac{\sum_{i=1}^k2^{p_{i-1}}3^{k-i}}{2^{p_k}-3^k}$$ where the set $p$ is an arbitrarily increasing set of positive integers. Explain why $f(k,p)$ is only natural when ...
1
vote
1answer
40 views

Analytic continuation of a series raised to a power raised to a power?

Background I recently realized I could construct the below formula: $$ \lim_{ x \to 1 }(1-x)(\sum_{r=1}^\infty b_r x^{r^\kappa} ) = (\sum_{\tilde r = 1}^\infty \frac{ b_\tilde r }{\tilde r ^\kappa})...
-2
votes
0answers
21 views

Imaginary number and fundamental theorm of algebra [on hold]

Is the fundamental theorm a consequence of way imaginary numbers were defined.? had we defined imaginary number in any other way, would the theorem be still true.? I am trying to find the usefulness ...
4
votes
2answers
63 views

What can I say of x given these conditions?

I know that $x^2-x$ is integer and also $x^n-x$ is integer for some $ n > 2$. Can I say that $x$ is integer? How can I show it? ($x \in \mathbb{R}$)
-1
votes
0answers
7 views

Prove by induction the feature:

If m,n are Natural Numbers, and $\frac{m^2}{n^2}<2$ prove by induction: $0<\frac{(m+2n)^2}{(m+n)^2}-2<2-\frac{m^2}{n^2}$ Step 1 To prove: $0<\frac{(m+2n)^2}{(m+n)^2}-2$ So: $0<\...
0
votes
0answers
18 views

Bounds for the number of prime factors of numbers of the form $2^k-1$

Let $t$ stand for numbers of the form $2^k-1$, $k$ a positive integer. Is it known whether $\Omega(t)-\omega(t)=O(f(\log t))$ where $f$ is sublinear? Here, $\Omega(t)$ is the number of not ...
0
votes
1answer
28 views

What is the definition of the least common multiple of elements of a group rather than their orders?

In an answer to my question here Relationship between order of $(x,y)$ in $G \times G'$ and order of disjoint permutations, which both involve LCMs?, it is said that Let $G$ be a group, $a\in G$...
5
votes
1answer
157 views

Is it true that there are infinitely many square numbers of the form $\lfloor n\sqrt{2}\rfloor$?

Is it true that there are infinitely many square numbers in the sequence $\left \lfloor n \sqrt{2} \right \rfloor $ with $n$ is a whole number? If not, how can we prove it?