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)

1
vote
1answer
253 views

Sequence of first differences strictly increasing?

If $ \pi (x) $ := number of primes $ \leq x $, the operation $T(x_{n+1}) = x_{n+1} - \pi(x_{n+1}) = x_n$ gives a sequence whose elements are those for which repeated application of T gives the ...
1
vote
1answer
270 views

Computing Hermite Normal Form using Extended Euclidean Algorithm (modulo $D$)

I am attempting to compute the Hermite Normal Form of a matrix $A$, again, only this time using the Extended Euclidean Algorithm modulo the determinant of the matrix. This was a method contributed by ...
1
vote
1answer
140 views

Conditional equivalence of expression to cardinality of primes on square intervals

This is an exercise to show that $$\frac{\pi((x+1)^2) - \pi(x^2)}{\pi(x- \pi (x)) } \sim 1 $$ assuming the unproven hypothesis: $\displaystyle \pi (x^2, x^2+x^{2( \theta)}) \sim \frac{x^{2( ...
1
vote
1answer
50 views

What do you call a finite set of maps on $\mathbb{Z}$ that are closed and compatible with operations on $\mathbb{Z}$?

Let $S$ be the set of maps and $\phi,\psi \in S$. Let $x,y \in \mathbb{Z}$. Suppose that $\phi(x) * \psi(y) = \nu(xy)$ for some $\nu \in S$. Then what would you call such a system of maps? If that ...
1
vote
1answer
106 views

A pattern in distribution of near-primes less than $2^n$

Let $\pi_k(2^n)$ be the number of almost-primes (numbers with k factors including repetitions) less than $2^n$. I noticed that for large values of n and values of k near n, a sequence $\{\pi_k\}$ ...
1
vote
1answer
125 views

constructing finite extensions with prescribed ramification

How does one construct (or show the existence at least) of a finite field extension $L$ of a complete discrete valuation field $K$ which ramifies totally over precisely one given prime ideal $p$ in ...
1
vote
1answer
69 views

Is it possible to store an integer in sub-logarithmic space?

The most intuitive method of representing an integer is in unary. For example, 10 can be represented as 0000000000, ----------, etc. This requires O(n) space. The most common method is slightly more ...
1
vote
2answers
1k views

How to work RSA encryption/decryption

I need an array populated with characters and integer keys for each, and I want to, using this set, encode messages, and then decode them later on . Essentially I am trying to write RSA algorithm for ...
1
vote
1answer
119 views

What are all pairs $(a,b)$ such that if $Ax+By \equiv 0 \pmod n$ then we can conclude $ax+by = 0 \pmod n$?

All these are good pairs: $$(0, 0), (A, B), (2A, 2B), (3A, 3B), \ldots \pmod{n}$$ But are there any other pairs? actually it was a programming problem with $A,B,n \leq 10000$ but it seems to have a ...
1
vote
1answer
346 views

Set of finite and cofinite subsets of the integers

Can I safely say that the set of finite and cofinite subsets of the integers equipped with operations of union and intersection is isomorphic to the direct product of countably infinitely many ...
1
vote
1answer
821 views

Is that improvement of Fermat factorization method?

Look at wikipedia link: http://en.wikipedia.org/wiki/Fermat%27s_factorization_method and look for basic method that is written there, where you have while loop. For every loop you have to square ...
1
vote
2answers
167 views

Sequences containing infinitely many primes

What are some interesting sequences that contain infinitely many primes? If it takes form of a polynomial, Dirichlet's theorem answer the question completely for linear polynomial. What about ...
1
vote
1answer
226 views

Constructing a homomorphism from class group to Sha.

In response to my previous question I got a wonderful answer from Prof.Emerton explaining about the similarities between $Ш$ and class group. In order to add something the comments I got from Mr. B R ...
1
vote
1answer
72 views

Looking for references on results on powers of primes dividing $y^n-1$

For a prime $p$ and positive integer $n$, let $E(n,p)$ be the greatest $k$ such that $p^k \mid n$, and $E(n,p) = 0$ if $p \nmid n$. Let $E(n) = E(n, 2)$. A number of years back, I proved the ...
1
vote
1answer
98 views

Given $a$ and $n$, find $y \equiv \frac{n!}{a^x} \bmod a$

Take $n!$ and find $x$, where $a^x$ is the greatest power of $a$ who divides $n!$ Then find $y$, where $y \equiv \frac{n!}{a^x} \bmod a$ For example, if $a=3$ and $n=6$ then ...
1
vote
1answer
98 views

Show that the numerator of $\sum_{k=1}^{p^2} \frac1k - \frac1p\sum_{k=1}^p\frac1k$ is divisible by $p^4$

Let $p\ge5$ be a prime. If the following fraction is fully reduced (to an irreducible fraction), prove that the numerator will be divisible by $p^4$. $$\sum_{k=1}^{p^2} \frac1k - ...
1
vote
1answer
527 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...
1
vote
1answer
204 views

squares ending with repeated digits

I am working on square ending in repeated digits in different bases. I have encountered the following problems during my work. can you generalize the following??? If the digit $a < p$ is a ...
1
vote
1answer
151 views

How can functions disagree with the values of its expansions at some points on an algebraic curve

I found a curve, in which some function has at least two expressions, which differ infinitely much!! Is there any error in the thoughts? The curve is defined by "$ ...
1
vote
1answer
189 views

Proving $\sum\limits_{k=1}^{\pi(n)-1} [ \theta(p_k) (1/{p_k}-1/p_{k+1})] -\ln(n)$ converges

Prove the sequence $a_n$ defined by $a_n = \sum\limits_{k=1}^{\pi(n)-1} [ \theta(p_k) (1/{p_k}-1/p_{k+1})] -\ln(n)$ converges, where $p_k$ denotes the $k$-th prime and $\vartheta(x)$ is Chebyshev's ...
1
vote
1answer
167 views

absolute value of norm of integral element

consider $\mathbb{Q}\subset K$ a finite algebraic extension. Take $x\in K$ integral, why $\mid Norm_{K/\mathbb{Q}}(x)\mid \geq 1$? Another question is: is it true that $\bar{\mathbb{Q}}_p \cong ...
1
vote
1answer
208 views

Prime numbers which solve $2^s=1\pmod p$

Here we define those primes $p$ for which $\operatorname{ord}_p(2)=s$, where $s$ is the minimum of the set $S$ of all divisors $d\mid p-1$ such that $2^d-1\geq p$. For example: for $p=7$, $s=3$, ...
1
vote
1answer
158 views

What 'special' properties do real quadratic fields have?

Sorry for the vague title... I've proved a number theoretical result for the imaginary quadratic fields (it was already known for the rationals). I think it would be much easier to sell if I could ...
1
vote
1answer
125 views

Number of digits in different number systems?

I know a similar question was asked before, but I wanted to know if this can be extended to any number system by a generic formula. For example, given a number X in number system A, how many digits ...
1
vote
1answer
74 views

How to map discrete numbers into a fixed domain?

I have several numbers, say 3, 1, 4, 8, 5, and I wanted them to be mapped into a fixed domain [0.5, 3]. In this case, 1 should be mapped as 0.5 and 8 is 3. Then the rest numbers should be scaled down ...
1
vote
1answer
217 views

Discrete logarithm to a primitive root base

I need to find out $\log_g {-1}$ in $\mathbb{Z}_n$ where $n$ is an odd prime and $g$ is a primitive root mod $n$. How do I do that? Thanks.
1
vote
2answers
243 views

A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$. I am inquisitive about how to approach this one?
1
vote
1answer
169 views

Proof for a fact involving $\mathrm{ord}_p(x)$

I'm reading Number Theory I, by Kato, et al. The authors claim that for $x$, $y\in \mathbb{Q}$ and $m$ a square free positive integer, if $2x$, $x^2-my^2 \in \mathbb{Z}$, then for any odd prime $p$ ...
1
vote
1answer
331 views

Invertibility of prime ideals in a number ring lying over prime numbers

I have trouble understanding an argument in the proof of the Kummer-Dedekind theorem. I am referring to a proof given in Peter Stevenhagen's notes. http://websites.math.leidenuniv.nl/algebra/ant.pdf ...
1
vote
1answer
77 views

Amicable Pair $(a, b)$: given $a$, what are limits on size of $b$?

Let any Amicable Pair be represented by $(a, b)$, with $a \lt b$. In a search for Amicable Pairs, let $(n, m)$ with $n < m$, be a candidate to be tested for being an amicable pair. Given $n$, is ...
1
vote
1answer
1k views

How are the taps of an LFSR found?

I'm reading through wikipedia about Linear Feedback Shift Registers (Specifically Fibonacci LFSRs) and the only restrictions it mentions about the taps are: The LFSR will only be maximum-length if ...
1
vote
1answer
260 views

How to calculate this set of diophantine equations

I am not a math expert nor a native English speaker, so maybe I am using wrong terminology... In this case, help me to improve my question :) Part 1: This is my set of equations, I have to calculate ...
1
vote
1answer
258 views

Proving that a Number is Relatively Prime in a sequence

Prove that a number in the sequence $2,3,4,...,n \ (n>2$, is relatively prime to all other numbers if and only if it is a prime that exceeds $\displaystyle\frac{n}{2}$. Does such a prime always exist? ...
1
vote
1answer
429 views

Calculate the remainder when there are division

Supose we have a set $S$ of natural numbers. We define: $$ f(x) = \begin{cases} {x \over 2} & x \text{ is even } \\ {x - 1 \over 2} & x \text{ is odd }\end{cases} $$ Now let $a_0 = a_1 = 1$ ...
1
vote
0answers
18 views

The Nagell-Ljunngren Equation

I have been trying to find the papers of Nagell and Ljunngren, which deal with the equation $$\frac{x^n - 1}{x - 1} = y^2$$ and solve it completely. Many papers cite these papers, but I haven't found ...
1
vote
1answer
21 views

What is the discriminant of $R:=\mathbb Z[\sqrt{2},\sqrt{3}]$?

What is the discriminant of $R:=\mathbb Z[\sqrt{2},\sqrt{3}]$ ? The discriminant is defined as the determinant of the matrix $\left(tr(x_ix_j)\right)_{1\le i,j\le n}$ for any basis ...
1
vote
0answers
9 views

Small proximity of important points of a function

Let a,b,c be coprime integers with a^2 + b^2 > c^2 and consider the function f(x) = a^x + b^x – c^x. It is easy to verify that there exist r and s such that f(r) ≥ f(x) for all x and f(s) = 0. Prove ...
1
vote
0answers
15 views

On the existence of a polynomial in several variables with only one zero

Given an ordered field $\mathbb{K}$, then for all $n>1$ there exists $f\in\mathbb{K}[X_1,\ldots,X_n]\ s.t.\ \mathcal{V}^{\mathbb{K}^n}(f):=\{p\in\mathbb{K}^n:f(p)=0\}=\{(0,\ldots,0)\}$ For ...
1
vote
1answer
18 views

Converting Unbalanced Ternary Numbers to Balanced Ternary Number

Can someone please provide a step by step algorithm for converting unbalanced ternary to balanced? for instance: (Base 10) 501 = (Base 3 Unbalanced) 200120 I've done some research on this conversion ...
1
vote
0answers
25 views

Prove that $a_{i,1}x_1 +a_{i,2}x_2 +···+a_{i,n}x_n ≤c_i, 1≤i≤n $ are all satisfied by a nonzero $n-tuple$ of integers.

My setting is that $c_1, · · · c_n$ are positive real numbers, and $A = [a_{i,j} ]$ is an $n × n$ non-singular matrix. Assume that $c_1 · · · c_n > | det(A)|.$ I want to prove that the n-linear ...
1
vote
0answers
52 views
+50

Product of Stirling Numbers of the first kind

I have been messing around with coefficients of various polynomials and was wondering if there was a way to reduce the following stuff. Let polynomial, ...
1
vote
0answers
33 views

Sums of triangles

If $P$ is any odd prime, is there a proof that working Mod P, each number from $0$ to $P-1$ except $\frac{(P^{2} -1)}{4}$ can be formed as the sum of the triangle of a number <(P+1)/2 and the ...
1
vote
0answers
19 views

Power series in p-adic integers

How can we show that for $x \in \mathbb{Z}_p$, $\log_p(1+x)$ converges in $\mathbb{Z}_p$ when $|x|_p < 1$? To clarify, $\log_p(1+x)$ is the power series: $$\sum_{n=1}^\infty ...
1
vote
1answer
46 views

What is behind these series?

I just found out (I am an amateur) that if I have the following series I get the following answers for the a nth number . (each series is the sum of the previous one) $$1 ,1 , 1, \dots, 1 $$ ...
1
vote
0answers
42 views

Number of pairs of integers $(a,b)$ with $a^2+b^2=n$ for a constant $n$ [duplicate]

Is there a more general formula for the number of pairs of nonnegative integers $(a,b)$ with $a^2+b^2=n$ for arbitrary $n$?
1
vote
1answer
49 views

Is $p\in\big\{x,…,2x\big\}$ lower-bounding $p\in\big\{x^2,…,(x+1)^2\big\}$?

Is it overreaching or erroneous to consider that possibility? (Alas, I'm not a mathematician, and don't have rigorous language to talk about this.) What I want to say is: Given any even span of ...
1
vote
1answer
14 views

What does it mean by “level sets of $\bar{G}$, a collection of forms, partition those of $\bar{F}$, another collection of forms”

I was reading an article and I was wondering if someone could explain me what a certain phrase meant. Let $\bar{F}$ be a collection of integral forms of degree less than or equal to $d$. And suppose ...
1
vote
2answers
27 views

How can a subgroup have multiple cosets?

I am currently reading An Introduction To The Theory Of Groups, by Joseph Rotman, and in a section describing cosets, there is an exercise question as follows; Let $H$ be and subgroup of $G$ having ...
1
vote
1answer
26 views

Gauss sum of character $\psi \neq 1$

I am trying to solve Let $1 \neq \psi$ be a charachter of $\mathbb{F}_p$ and define $$G(\psi) = \sum_{x\in \mathbb{F}_p} \psi(x^2) $$ Proof that $|G(\psi)|^2 = p$. What I tried so far: ...
1
vote
0answers
34 views

Generator of group, Computation of discrete logarithm

The prime number $p=67$ is given. Show that $g=2$ is a generator of the group $\mathbb{Z}_p^{\star}$. Compute the discrete logarithm of $y=3$ as for the base $g$ with Shanks-algorithm. Compute the ...