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.
26,743 questions
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?
