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)

0
votes
1answer
16 views

Parametrization of solutions of diophantine equation $x^2 + y^2 = z^2 + w^2$

I need integer solutions of $x^2 + y^2 = z^2 + w^2$ parametrized. Can it be done? Thanks.
0
votes
0answers
6 views
1
vote
1answer
34 views

Show that $-1=\sum_{0}^{\infty} (p-1)p^i$ in $\mathbf{Q}_p$

To show that in the field $\mathbb{Q}_p$, where $p$ is a prime, it holds that: $$-1=\sum_{0}^{\infty} (p-1)p^i$$ I did the following: It suffices to show that: $\left|\sum_0^N (p-1)p^i+1 \right|_p ...
0
votes
1answer
34 views

A fast method for factorizing $2^p-1$

I know that $\forall{d,n\in\mathbb{N}}:d|n\implies2^d-1|2^n-1$. Now, suppose that $n$ is prime - is there any fast algorithm for finding a divisor of $2^n-1$? By "divisor", I am referring to a ...
0
votes
3answers
47 views

Inductive step in proof of Freshman's Dream

I am trying to prove that for $K$ a field of characteristic $p$ prime, $q$ a power of $p$ and $x,y$ in $K$, $$(x+y)^q=(x^q + y^q).$$ I have the base case, and now I am trying to do the inductive ...
0
votes
1answer
13 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
3
votes
1answer
62 views

$\sqrt{m_1}+\sqrt{m_2}+ \cdots + \sqrt{m_n}$ is Irrational [duplicate]

If $m_1 , m_2, \cdots m_n$ are natural numbers where at least one of them is not a perfect square, then how do I prove that the sum $$\sqrt{m_1}+\sqrt{m_2}+ \cdots + \sqrt{m_n}$$ is irrational? I'm ...
0
votes
0answers
11 views

To solve the system of Diophantine equations.

I decided to compile a single task and to record such a system. $$\left\{\begin{aligned}&xt+yw=az^2\\&xw-yt=br^2\end{aligned}\right.$$ $a,b - $ integers that are the problem. It is clear ...
1
vote
1answer
22 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
0
votes
1answer
46 views

If $a^2$ divides $b^3$, then $a$ divides $b$.

I want to prove or provide a counterexample to the following statement: $a^2|b^3 \Rightarrow a|b$. I know that $a^k|b^k \Rightarrow a|b$. My thought is that, e.g in the case of $k = 3$, where we ...
0
votes
1answer
26 views

$f(x)=x^2-a \in \mathbb{Z}[x]$ - show propositions

Let $f(x)=x^2-a \in \mathbb{Z}[x]$. $$p \in \mathbb{P}, p \neq 2, p^2 \nmid a$$ The equation $f(x)=0$ If $p \mid a $, the equation has no solution in $\mathbb{Q}_p$ Let $p \nmid a$. The ...
0
votes
1answer
28 views

Integer factorization simplification

I found a small improvement to the brute force algorithm for the Integer Factorization. Please tell me if there is a point to investigate it more or there are better similar ideas. I found that if ...
0
votes
1answer
29 views

Closed Form of n(mod7) [on hold]

For an integer n,what is the closed form as a function of n, if it exists, of n(mod7)={0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,...,n(mod7)}? The closed form of n(mod8) uses trigonometric ...
1
vote
1answer
36 views

pth root of unity in $p$-adic field

It is well known that $\mathbb{Q}_p(\mu_n)$ is a totally ramified extension of degree $(p-1)p^n$ if $\mu_n$ is a primitive $p^n$th root of unity. However how true is this statement for a finite ...
1
vote
1answer
36 views

Question about the proof of Hensel's Lemma

Hensel's Lemma: Let $F(x)=\alpha_0 + \alpha_1 x+ \dots + \alpha_n x^n \in \mathbb{Z}_p[x]$. We suppose that there is a $p$-adic $a_1 \in \mathbb{Z}_p$ such that $$F(a_1) \equiv 0 \mod p ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
3
votes
1answer
33 views

There is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m \mid (p-1)$

After Hensel's Lemma there is the following proposition in my notes: If $p$ is a prime and $m \in \mathbb{N}$ then there is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m ...
0
votes
0answers
12 views

The equation $P(X,Y)$ has a solution in $\mathbb{Q}_p$

Proposition Let $P(X,Y) \in \mathbb{Z}[X,Y]$. The following propositions are equivalent: The equation $P(X,Y)$ has a solution in $\mathbb{Q}_p$. For each $n \geq 0$ the equation $P(X,Y)$ has a ...
3
votes
2answers
79 views

Inverse limit of $\mathbb{Z}/n\mathbb{Z}$

I know that this is well-known fact that $$\lim\limits_\leftarrow\mathbb{Z}/n\mathbb{Z}=\prod\limits_p\mathbb{Z}_p,$$ however I don't know the rigorous proof of this. Can anyone give me the ...
2
votes
0answers
28 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...
-3
votes
0answers
28 views

analysis/number theory study group (online) [on hold]

I plan on studying analysis from landau, rudin probably others and am looking for people (hopefully more than 1) where we could solve theorems/problems and ask each other questions. Online ...
5
votes
2answers
56 views

Proving that $\sin1 $(radian) is irrational without using Taylor Series Expansion.

In university last semester I was asked to prove that $\sin1$ (1 radian that is) is irrational, and ended up simply using the Taylor Series Expansion. This method provides a very quick solution, but ...
2
votes
3answers
49 views

Counting the number of $\mathbb{F}_q$ points on a homogeneous polynomial

This is an area of number theory that I am not too familiar with and I would appreciate any assistance! Let $\mathbb{F}_q$ be a finite field of $q$ elements with characteristic not 2 or 3. I have the ...
4
votes
0answers
30 views

Can we find the GCD of two polynomials in $\mathbb Q[x]$ by representing the coefficients as vectors?

Can we find the GCD of two polynomials in $\mathbb Q[x]$ by representing the coefficients as vectors? For example: $f=x^5+3x^4+x^3+4x^2+1$, and $g=x^5+3x^4+4x^3+3x+1$ Can we represent these ...
1
vote
1answer
65 views

Intuituive reason why Fermats last theorem holds

I am unsure of whether it is normal, but to me, intuitively Fermats last theorem should not hold. If anyone intuitively believed it to be correct, why? Can someone explain so I understand ...
1
vote
1answer
26 views

How do we deduce that $\mathbb{Q}_p=\{ p^mu\mid u \in \mathbb{Z}_p^{\star}, m \in \mathbb{Z}\} \cup \{0\}$?

We know that each element $x$ of $\mathbb{Z} \setminus{\{0\}}$ has a unique representation of the form $x=p^m u\mid m \in \mathbb{N}_0, u \in \mathbb{Z}_p^{\star}$. $$\mathbb{Q}_p=\left \{ ...
1
vote
2answers
52 views

Prove that $\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$ is divergent

In this question I've asked to decide the convergency of the series $\sum_{p \in \mathcal P} \frac1{p\ln p}$. Now I ask you to show that the series $$\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$$ ...
1
vote
1answer
34 views

What is the probability that a random K-bit odd-number is prime?

Is it $e/K$? In an experiment that created 1000 random RSA-2048 key-pairs, 2000 random 1024-bit primes were created. It turned out that $727,709$ random candidates were generated, to create 2000 ...
2
votes
0answers
37 views

Generalizing in Mathematics

I was reading the book "Fermat's Last Theorem" by Simon Singh when it hit me that this theorem is so contrived, andyet it lead to several important breakthroughs in mathematics and especially the ...
0
votes
0answers
21 views

Continued fraction approximation

Let $\theta\in\Bbb{R}_{\gt0}$. A) Prove that the convergents for the continued fraction expansion of $\theta$ give us better and better rational approximations to $\theta$. B) Suppose $\theta\notin ...
2
votes
2answers
30 views

a root of some polynomial over finite field

I think this is a really basic question, but it had been a little while since I dealt with this material and I was hoping to get a bit of assistance here. Let $q = p ^{2M}$ for some prime $p$ and $M ...
0
votes
0answers
59 views

Idele for a rational number $q=\frac{63}{550}$ [on hold]

Wikipedia, in its article "p-adic number", has taken an arbitray number $x= \frac{63}{550}$ to show the p-adic absolute value with respect to different primes. Obviously, the p-adic absolute value is ...
0
votes
1answer
14 views

solve $k(k-1) \geq \ln2*2m$ for k

My Question is related to the birthday problem. Starting at $e^{-\frac{k(k-1)}{2m}} \leq 0.5$ i used $ln(x)$ on both sides and multiplied by $-2m$ to get $k(k-1) \geq \ln2*2m$ According to my ...
0
votes
1answer
53 views

The diophantine equation $a^7+b^7=7^c$

Determine all the triples of positive integers $a,b,c$ such that $a^7+b^7=7^c$.
1
vote
1answer
32 views

If $a+bi$ is in $E_k$ then $a-bi$ is also in $E_k$?

I'm currently studying the properties of the Motzkin sets $E_k$, $k\in\mathbb{N}\cup\{0\}$ of the ring $\mathbb{Z}[i]$. The definition of $E_k$ is as follows: $E_0=\{0\}$, $E_1=$units of ...
0
votes
2answers
49 views

Understanding why the public exponent $e$ is chosen the way it is in RSA

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities ...
2
votes
0answers
34 views

Transforming the cubic Pell-type equation for the tribonacci numbers

The Lucas and Fibonacci numbers solve the Pell equation, $$L_n^2-5F_n^2=4(-1)^n\tag1$$ The tribonacci numbers $z = T_n$ are positive integer solutions to the cubic Pell-type equation, $$27 x^3 - 36 ...
2
votes
2answers
39 views

Solving Linear Congruences With The Euler Totient Functio

I've been asked to calcualte $15^{123456789012345}$ mod $2500$. Now I worked out $\varphi(2500)=1000$ but I can't use Euler's theorem here because $1000$ and $2500$ aren't coprime. Can anyone offer ...
1
vote
1answer
48 views

Every element of field $F_q$ has $k$th root if and only if $\gcd(q-1,k)=1$

Help me please to prove that: For any $k \in \mathbb{N}$ each element of field $F_q$ is the $k$-th power of some element from that field if and only if $GCD(q-1, k)=1$. My approach Let's look ...
1
vote
1answer
29 views

Solving Linear Congruences With Euler Totient Function

I've been asked to solve the following congruence $x^{1667}\equiv2$ $mod$ $2500$. Am I right in saying there's no solution modulo 2500 to this congruence since even though 1667 is coprime to ...
0
votes
0answers
31 views

Polynomial/ Exponential diophantine equation

I am looking for the reference characterizing all the cases when $$an^2+bn+c=2^m$$ has infinitely many positive integer solutions (m,n). Thanks.
3
votes
1answer
49 views

Solving A Certain Diophantine Equation

I am stack on finding the solution of the diophantine equation: $d(2^{k+1}-1)-b^2(2^{k+1}-2)=1$. where $k\geq 1$ and $b^2>d$ for $b$ an odd composite integer. Is there a solution to this ...
0
votes
0answers
32 views

Number theory and Group theory [on hold]

Can you give me any task which contains Number theory and Group theory?
8
votes
2answers
103 views

A number $N$ is a $k$-nacci number if and only if …

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ ...
1
vote
0answers
27 views

e Online source for alternative proofs

I'm looking for some alternative proofs for various theorems. My goal is to compile a list of various proofs each relating to a specific theorem (such as the triangle inequality, Fermat's Little ...
2
votes
3answers
97 views

Collatz conjecture: Largest number in sequence with starting number n

This question is inspired by a CS course, and it only tangentially relates to the actual content of the exercise. Say in a hailstone sequence (Collatz conjecture) you start with a number n. For any ...
1
vote
1answer
38 views

All possible number combinations in decimal represenation of irrational numbers?

This question is directly inspired by "Does Pi contain all possible number combinations?". I would like to state firstly for the record that I have no serious number theory education. I think I ...
3
votes
1answer
29 views

Asymptotic formula for sums of powers of reciprocals of primes

Is there an explicit asymptotic formula, in terms of $\alpha$, for the expression $$\displaystyle \sum_{p \leq x} \frac{1}{p^\alpha}$$ for $0 < \alpha < 1$? The case $\alpha = 1$ is supplied by ...
1
vote
0answers
32 views
+100

On a congruence for the number of finite topologies

I am making search about "On a congruence for the number of finite topologies". I have found a paper. I guess it is written in Russian. How can I find English version of this paper ? I am also ...
3
votes
1answer
31 views

Origin of period function model of primes

There is a web page attributed to Omar Pol, "Sobre el patrón de los números primos: Determinación geométrica de los números primos y perfectos." ("On the pattern of primes: Geometric Determination of ...