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
0answers
10 views

When does Fermat's Last Theorem hold over finite fields?

It is well-known that in his attempts to prove Fermat's Last Theorem (FLT) over $\mathbb Z^+$, Schur came up with a result that has come to be known as Schur's Theorem, which implies that FLT fails ...
0
votes
0answers
9 views

The concept of associate for finite abelian groups

Let $G$ be a finite abelian group of order $n$, and let $a$ and $b$ be elements of $G$. If $a$ generates the same subgroup as $b$, must there be an integer $i$ prime to $n$ such that $ia=b$? I can ...
1
vote
1answer
33 views

$x^2\equiv 5 \pmod{1331p^3}$

Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to $$ x^2\equiv 5 \pmod{1331p^3} $$ I began the problem by splitting ...
0
votes
1answer
48 views

Questions on two Formulas for $\zeta(s)$

This question is related to the following two formulas for $\zeta(s)$. (1) $\quad\zeta(s)=\frac{1}{1-2^{1-s}}\sum\limits_{n=0}^\infty\frac{1}{2^{n+1}}\sum\limits_{k=0}^n\frac{(-1)^k\binom{n}{k}}{(k+1)...
1
vote
1answer
40 views

How “deep” is the theory of encryption keys? Can a “generalist” approach it or does one need to be a number theorist?

How "deep" is the theory of encryption keys? Can a "generalist" approach designing new keys or understanding state of the art "security" or does one need to be a number theorist?
1
vote
1answer
22 views

Erdős-Straus-conjecture using polynomials in Python

I am trying to write a code in Python to do the following. We can express the Erdős-Straus-conjecture in function of some polynomials $x(k), y(k), z(k) \in \mathbb{Q}[k]$ such that $\frac4k = \frac{1}...
-2
votes
1answer
18 views

How to find prime factors p and q from having ϕ(n) [on hold]

Given ϕ(n) or the number of positive integers relative prime to n, how to find distinct primes p and q?
1
vote
2answers
36 views

Proof relatively prime numbers

Let $p,q,r$ be three distinct prime numbers and $m = p*q*r$. How many of the numbers {$1,2,...,m$} are relatively prime to $m$? I tried to do it for: a) $m=2*3*5=30$, b) $m=2*3*7=42$, c) $m=3*5*...
2
votes
0answers
21 views

Is Hom scheme between projective curves of large genus finite etale?

Let $K$ be a number field, $T$ be a finite set containing some finite places of $K$, and $S=\operatorname{Spec} O_{K,T}$. If $X,Y$ are two projective smooth curves over $S$ with genus large than $1$ ...
1
vote
2answers
37 views

Average power of 2 in all even natural numbers

Consider all even natural numbers. Every 4th number has a power of 4 (or $2^2$) Every 8th number has a power of 8 (or $2^3$) Every 16th number has a power of 16 (or $2^4$) What is the average ...
0
votes
2answers
38 views

Do two equivalent quadratic forms necessarily have the same solutions

Do two equivalent quadratic forms necessarily have the same solutions? Suppose that I have $Q(x,y)= x^{2}- xy+ 8y^{2}$ and $R(x,y)= 2x^{2}+ 3xy+ 5y^{2}$ and the value of $Q(2,1)$ and $R(2,1$) are ...
0
votes
0answers
21 views

Existence of mod $m^n$-points for every $n$

Let A be a complete noetherian local ring and $m$ be its maximal ideal. If I have some polynomials $f_i$ with coeffecients in $A$, and they have a common zero $x_n$ in $A/m^n$ for every $n$, then must ...
2
votes
1answer
25 views

A sequence of thirteen integers…if every selection of twelve terms from the sequence contains six terms…

This is a delightful Oxford entrance question from 1993, but I'm stuck on the final bit. A sequence $$N_1, N_2, N_3, ..., N_{13}$$ of thirteen integers is said to be lucky if every selection of ...
0
votes
0answers
19 views

How to: $f(x)$ congruent to $a \pmod{b^n}$

I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class. The specific question is ...
0
votes
2answers
36 views

Infinitely many consecutive primes with difference greater than 2. [on hold]

Let $p_k$ be the $k$-th prime number. Show that there are infinitely many $k$ such that $$p_{k+1} − p_k > 2$$. Suppose If this is not true then won't that contradict the twin-prime conjecture?
1
vote
2answers
23 views

About The Sum of Positive Divisors of $n$

The question says: Find the smallest positive integer $n$ so that $\sigma(x)=n$ has no solution, exactly two solutions, exactly three solutions. I could not come up with a good way to solve this ...
0
votes
1answer
59 views

How do I prove the following using Fermat's theorem on sums of two squares?

For naturals $x_i,\,y_i$ with $1\le i\le 2019$, $\prod_i (2x_i^2+3y_i^2)$ is not a perfect square.
3
votes
1answer
31 views

For what primes $p \nmid \gcd(a,b,c)$ does $p \mid a+b+c \implies p \nmid a^2+b^2+c^2$?

Let us have prime $p$ such that $p \nmid \gcd(a,b,c)$ and $p \mid a+b+c$. For what primes is it then impossible for $p \mid a^2+b^2+c^2$ ? One example of such a prime is $p=5$: If $5 \mid a^2+b^2+c^...
3
votes
1answer
42 views

Integral Closure, Galois extension,and Dedekind Domain

Let $A$: Dedekind domain, $K$: $\operatorname{Frac}(A)$, $B$: Dedekind domain with $A \subset B$, $L$: $\operatorname{Frac}(B)$ Let $L/K$: galois extension with galois group: $G$. $B^G=\{b \in B \...
0
votes
0answers
31 views

Find a congruence condition that determines whether $5$ is a square modulo $p$

Let $p\not\in\{2,5\}$ be prime. How can I find a congruence condition that determines whether $5$ is a square modulo $p$?
0
votes
0answers
23 views

Probability that a natural number is a k-th power

I would like to determine the probability that a natural number is a k-th power. It is quite straightforward to see that the probability for a natural number less than N to be a I-that power is $$N^{1/...
1
vote
2answers
25 views

The totient of a factor of a number divides the totient of the number.

Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
2
votes
0answers
20 views

Explanation of the Wolstenholme theorem proof

I recently came accross the Wolstenholme theorem which says that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod {p^{3}}$$ On wikipedia, it gives a combinatorial proof of this theorem that involves ...
0
votes
1answer
21 views

Given an odd prime p, how do we know that there is a number making the legendre symbol equal to -1? [on hold]

Given an odd prime $p$, does there must exist a number $a$, such that $\big(\frac{a}{p} \big) = -1$.
0
votes
0answers
29 views

A bridge between the sum of the divisors and the Totient function

Let's consider: $$\tau(x,a,b)=\sum_{1 \le d \le x \\ (d,x)=d^a \\} d^b$$ Where $(q,r)$ denotes the gcd of $q$ and $r$. I think this could be interesting thing to look at because it's somehow a ...
1
vote
3answers
73 views

Find all positive integers $a$ and $b$ such that $(1 + a)(8 + b)(a + b) = 27ab$.

Here's the problem I'm having difficulties with: Find all positive integers $a$ and $b$ such that $$(1 + a)(8 + b)(a + b) = 27ab\,.$$ Does anyone have an idea how to do this? Any detailed solution ...
1
vote
0answers
10 views

Symmetric continued fractions property

Let $[a_0,a_1,a_2,\ldots,a_n,a_n,\ldots,a_2,a_1,a_0]=:\frac{p}{q}\in\mathbb{Q}$ be a symmetric continued fraction. This sequence of $a_i$'s consists of finitely many elements because $\frac{p}{q}$ is ...
0
votes
0answers
52 views

The sum of nested integer partitions

Please observe the following diagram of the natural numbers 1 to 4: This diagram represents the transition from multiplicity to addition under a given natural number > 0, such that multiplicity is ...
-2
votes
2answers
42 views

Integer solutions to $\sqrt{x^{2}+x+1}=n$?

Is there an integer solution to $\sqrt{x^{2}+x+1}=n$ where $n$ is a natural number? (besides $x=0$, $n=1$) I don't even know how to approach this, but I need it for a proof.
1
vote
1answer
32 views

Is it true that every pythagorean triples is of the form $(a^2-b^2)^2+(2ab)^2=(a^2+b^2)$?

For example, the Pythagorean triples $(3,4,5)$ is $(2^2-1^2)^2+(2\times2\times1)^2=(2^2+1^2)^2$.
0
votes
0answers
27 views

How can I find the exponent $n$ efficiently?

Denote $$z=(2^{19}-1)\cdot10^6+2^{18}-1$$ $$a=ord_2(z)$$ $$b=ord_{10}(z)$$ The object is to find a positive integer of the form $$n=ka+19$$ with positive integer $k$ such that $$m=f(n)=\lceil(n-1)\...
0
votes
1answer
22 views

Arriving at odd possible solutions for functions

Say $f(x)=\dfrac{3x+1}{2}$ I want to find out for which values of $x$ is the value of $f(x)$ an odd number. So I reframe $f(x)$ to $\dfrac{3x+1}{2}=2k_1+1$ on simplifying further... $\dfrac{3x-1}{...
2
votes
1answer
51 views

Integer equations

I have $2$ following problems. Find integer roots of $$\begin{align} &1)~\frac{x+y}{x^2-xy+y^2}=\frac3z \\ &2)~x^3y^3-4xy^3+y^2+x^2-2y-3=0 \end{align}$$ I have no idea to solve them. I try ...
2
votes
2answers
48 views

Let $r$ be primitive root mod $p$. When $x$ goes from $1$ to $p-1$, then $r^x$ (mod $p$) goes through all the numbers $1,\dots,p-1$ in some order

I'm trying to understand this situation. Why do the powers of primitive roots smaller than $p-1$ generate all DISTINCT elements in $\mathbb{Z}_p$? I am aware about what Fermat's little theorem states ...
-4
votes
0answers
33 views

Should an Elementary Fermat's last theorem proof relate to squares and triangles? [on hold]

I am asking this in regard to developing a framework using first principal thinking and discovery method. As I have rote & Learning disabilities so I had to teach myself in many regards. The ...
0
votes
0answers
21 views

Consider an RSA Public Key Cryptosystem with n = 2867 [on hold]

Find the two prime numbers whose product is n 5.2 Let the public key be (17, 2867). Find the private key (t, 2867) 5.3 Compute the encryption of 2501. Perform a mod operation after each multiplication ...
3
votes
2answers
44 views

Integrality of a certain quantity $\sum_{i =1}^n a_{\lfloor \frac{n}{i}\rfloor }=n^{10}, $

Problem :A sequence $a_1,a_2,\dots$ satisfy $$ \sum_{i =1}^n a_{\lfloor \frac{n}{i}\rfloor }=n^{10}, $$ for every $n\in\mathbb{N}$. Let $c$ be a positive integer. Prove that, for every positive ...
-1
votes
0answers
42 views

what is a the differential form of the Riemann zeta function?

So I understand the function and the summation as: $\sum_{n=0}^{\infty} 1/n^a= \zeta(a) $ but I recently came across a term as : $d \zeta(a)$, but I don't know how to interpret this. The function ...
0
votes
0answers
14 views

Thoughts on Lehs conjecture $\forall n>2\in \mathbb N\exists a,b\in \mathbb N$ such that $a+b=n\land (a+ab+b)\in \mathbb P$. Lehs comet?

Lehs conjectured here that $\forall \ n>2\in \mathbb N,\exists\ a,b\in \mathbb N$ such that $a+b=n\land (a+ab+b)\in \mathbb P$. In comments, Crostul restated this as $\forall \ n\ge 4\in \mathbb N,...
3
votes
1answer
68 views

Solving the Diophantine equation $y^3 = 4x^2+4x+ 5$ for $x,y \in \mathbb{Z}$

I want to solve the Diophantine equation $y^3 = 4x^2+4x+ 5$ for $x,y \in \mathbb{Z}$. The right hand side factors as $(2x+1-2i)(2x+1+2i)$. Am I right that such a factorization can be found using the ...
0
votes
3answers
43 views

Showing that the Diophantine equation $3x^2 + 6y^6 + 1 = 8xy^3$ has no solutions $x,y \in \mathbb{Q}$

I want to show that the Diophantine equation $3x^2 + 6y^6 + 1 = 8xy^3$ has no solutions $x,y \in \mathbb{Q}$. I tried factoring, but didn't manage (but I'm not good at factoring). Then I tried ...
1
vote
2answers
53 views

Solving the Diophantine equation $y^2 = x^4+x+ 2$ for $x,y \in \mathbb{Z}$

I want to solve the Diophantine equation $y^2 = x^4+x+ 2$ for $x,y \in \mathbb{Z}$. I already found 4 solutions: $(x,y) = (1,\pm2)$ and $(x,y)=(-2,\pm4)$. It can probably be solved using some ...
0
votes
1answer
50 views

A simple equation with a complicated property

Let, $\Bbb{P}$ denote the set of all odd prime numbers and $\Bbb{N}$ be the set of all natural numbers. Let, $2a,2b$ be two even numbers both greater than $4$. Define, $A=\{(p,q)\in\Bbb{P}\times\Bbb{...
2
votes
1answer
36 views

Large Carmichael number

I need to find or generate a very large Carmichael number (500 digits or longer). I've tried to find a database or just an example of such a number but failed. Is there any examples of really big ...
1
vote
0answers
14 views

Am I right in this proof of a criterion for the nonsingularity of a conic curve?

$\newcommand{\C}{\mathcal{C}}$ This is an exercise in Silverman and Tate's Rational Points on Elliptic Curves: Let $\C$ be the conic given by the equation $$ F(x,y)=ax^2+bxy+cy^2+dx+ey+f=0.$$ ...
0
votes
0answers
48 views

About $\varphi(n)$ I don't know how to get? [on hold]

$$ \sum_{n\mid m}\sum_{d\mid n}d\varphi\left(\frac{n}{d}\right) =\sum_{n\mid m}\sum_{i\mid \frac{m}{n}}n\varphi(i)\\ =\sum_{n\mid m}n\frac{m}{n}=m\sum_{n\mid m}1 $$ so, how to get this? $$ \sum_{n\...
0
votes
0answers
17 views

Invariant remainder [on hold]

How can I find a number $n$ for which different integers devided by $n$ give the same remainder?
0
votes
3answers
45 views

Prove $3^x+9^x+1$ is divisible by 13 if $x=3n+1$

I don't know how to start thinking about this problem, I was going to try to prove it by induction, but I think I'm on the wrong path. Any hints?
0
votes
2answers
34 views

Find the least nonnegative residue of: $42^{173} modulo 13$

I can across this question: Find the least nonnegative residue of: $42^{173} modulo 13$ I have done the following: $42^{10} ≡ 1 mod 13$ $42^{173} = 42^{10 (17) +3}$ $ 42^{173} ≡ 42^{3} mod 13$ $...
3
votes
3answers
44 views

$(m,n)=1$, what could $(3n-4m, 5n+m)$ be?

This is what I have so far: let's say $d$ is the common divisor of $3n-4m$ and $5n+m$, then $d$ divides $5(3n-4m)-3(5n+m)=-23m$ and $3n-4m+4(5n+m)=23n$. $d$ can't be a divisor of both $m$ and $n$, so ...