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

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
0
votes
2answers
24 views

Chinese Remainder theorem with non-pairwise coprime moduli proof

There exists a $x \in \mathbb{Z}$ satisfying system of equations: $$x=a_1 \pmod {n_1}$$ $$x=a_2 \pmod {n_2}$$ $$\ldots$$ $$x=a_k \pmod{n_k}$$ if and only if $a_i=a_j \pmod{\gcd(n_i,n_j)}$ for all ...
0
votes
0answers
13 views

Pollard method for finding prime divisor.

Use the Pollard $p-1$ method to find a prime divisor of $7,331,117$. How do you do this using just a calculator ?
0
votes
1answer
18 views

series for $n$-th prime number and prime counting function

"Theoretical Computer Science Cheat Sheet" gives the following: $$p_n = n \ln n + n \ln \ln n - n + n \frac{\ln \ln n}{\ln n} + \mathcal{O}\left( \frac{n}{\ln n}\right)$$ $$\pi (n) = \frac{n}{\ln n} + ...
2
votes
0answers
51 views

Are there infinite many primes p such that 2p-1 is also prime?

I did a search online and found a similar notion called Sophie Germain prime, which by definition is a prime $p$ such that $2p+1$ is also prime. Sophie Germain primes are conjectured to be of infinite ...
4
votes
3answers
706 views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
2
votes
2answers
39 views

Prove that $\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)$

How can I prove: $$\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)?$$ Few observations : Left side is a sum function and the right side is a number of divisors function. Both the sides ...
4
votes
3answers
59 views

Prove that there are infinitely many primes $P_i\equiv1\pmod6$

Proving that there are infinitely many primes is fairly simple: Assume that there is a finite number of primes. Let $G$ be the set of all primes $P_1,P_2,...,P_n$. Compute $K = P_1 \times P_2 \times ...
3
votes
2answers
61 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
2
votes
3answers
98 views

Is there a name for this pattern?

I'm not a mathematician, but I was calculating multiplication of some numbers and I saw a pattern emerging. What is this phenomenon called? And does it happen in other cases? ...
2
votes
0answers
39 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
3
votes
4answers
79 views

If $q^n$ is irrational for all $n>1$, then $q$ is irrational.

Theorem. Let $q \in \mathbb{R}$ an arbitrary given number. If $q^n$ is irrational for all $n>1$ integer, then $q$ is irrational. My Questions. What is a the name of this statement and what is the ...
5
votes
0answers
81 views

Has category theory solved major math problems?

All: I am new to category theory. Just wonder if category theory has solved any major math problems for other mathematics fields? or what are the major applications of the category theory ? ...
4
votes
0answers
45 views

What are major algebraic number theory attempts, results and progressions toward Goldbach's Conjecture?

To my understanding, most progress toward Goldbach's Conjecture has been made in analytic number theory. Progress has often based on sieve, asymptotic estimation or other analytic methods. What are ...
1
vote
1answer
22 views

Can the natural numbers be defined in terms of the non-trivial zeta zeros?

Can the natural numbers be defined in terms of the non-trivial zeta zeros? Presumably they can, since $\pi(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^\rho),$ and $\zeta(s)=\sum ...
0
votes
0answers
22 views

Minimum Positive value of a linear equation

What is the minimum positive value of $$f(x,y)=Ax+By$$ where x,y are inetegers. Is it $\gcd(A,B)$? Can anyone explain what the answer is...
0
votes
2answers
21 views

Proportionals and squares

Let $a,b,c,d \in \mathbb{Z^+}$ and $a:b::c:d$ and $ac$ is a square. Can we prove that $bd$ is a square too?
0
votes
0answers
31 views

Subring of $\mathbb{Z}[i]$ and an infinite set $X$ such that $\exists x \forall y \in X \,\,x^2\mid y^2$ but $\forall x \forall y \,\,x \not\mid y$

This is a question derived from A subring of the ring of Gaussian integers such that $a^2 \mid b^2$ does not lead to $a\mid b$ in infinitely many such cases. Is there a subring $R$ of Gaussian ...
2
votes
0answers
38 views

What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers and the integer

As we know,$\sqrt{2} = [1;2,2,2,2,…]$; while $\sqrt{14}= [3;1,2,1,6,1,2,1,6…]$,let $L$ the length of period of simple continued fraction expansion of quadratic algebraic numbers be the number of ...
0
votes
1answer
46 views

A subring of the ring of Gaussian integers such that $a^2 \mid b^2$ does not lead to $a\mid b$ in infinitely many such cases

As the ring of Gaussian integers is a UFD, this means that $a^2 \mid b^2$ leads to $a\mid b$. Is there any subring of the ring of Gaussian integers with infinitely many elements such that ...
2
votes
1answer
51 views

How to determine if an equation is a rational variety?

Is there an easy way to determine if a given equation is a rational variety? For example, is $x^3+y^3+z^3=3$ a rational variety? I have maxima installed on my computer, if that helps.
1
vote
0answers
34 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
2
votes
1answer
75 views

How prove this there many infinite numbers postive ineteger $n$ such $n^3+1|n!$

Question: show that: there exsit infinite postive integer $n$ such $$n^3+1|n!$$ Buy the way,I know prove this this simple problem: prove there are many infinte postive integer numbers ...
3
votes
2answers
45 views

How prove or disprove $12^n-11^n=p^a$

Let $p>11$ be a prime number, prove or disprove that there exists a composite number $n$ and a positive integer $a$, such that $$12^n-11^n=p^a$$ I have looked up all $n\le 10$, and I ...
3
votes
2answers
54 views

What is the greatest common divisor of $3^{3^{333}}+1$ and $3^{3^{334}}+1$?

What is the greatest common divisor of $3^{3^{333}}+1$ and $3^{3^{334}}+1$ ? Could somebody please help me ?
2
votes
1answer
42 views

Silly number theory questions I can't prove.

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
8
votes
2answers
508 views

Is 641 the Smallest Factor of any Composite Fermat Number?

Consider the sequence $a_n = 2^{2^n}+1$ of so-called Fermat numbers. It's well known that $a_5$ isn't prime ($a_5 = 641 \cdot 6700417$, this is due to Euler). What I want to know about this sequence ...
-1
votes
1answer
46 views

Suppose f(x) + 2f(1/x) = x . Evaluate f(5) in simplest form. [on hold]

If f(x) + 2(f(1/x)) = x, evaluate f(5). How can I go about solving this problem?
0
votes
1answer
41 views

Density of $\{n^2x\}$ in $(0, 1)$ [on hold]

If $\{y\}$ is the fractional part of $y$, is $\{n^2 x\}$ dense in $(0, 1)$? Here $x$ is an irrational in $(0, 1)$ and $n$ is any integer.
4
votes
2answers
41 views

Heuristic for Dirichlet's Theorem on Arithemtic Progression

If we let $\pi_{a,d}(x) = \{p \leq x: p \mbox{ prime, } p \equiv a \mod{d}\}$ then it is a well known result that if $(a,d)=1$ then $$\lim_{x \to \infty} \frac{\pi_{a,d}(x)}{\pi(x)} = ...
5
votes
3answers
48 views

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ My try : Left hand side : $\begin{align} \sum_{d|p^k}\sigma (d) &= \sigma(p^0) + \sigma(p^1) + ...
6
votes
1answer
31 views

What is the smallest $d$ such that $4$ has more than one distinct factorization in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$?

Or if there is no such $d$, how do I prove it? Obviously there is no point to looking for this in an UFD. I've looked in other rings, and each time I think I found it, I divide one of the factors by ...
0
votes
0answers
39 views

The structure of certain quotients of a ring of algebraic integers by a principal ideal

Let $\mathcal{O}_K$ be the ring of algebraic integers of a number field defined by a cubic polynomial $P$, and let $\mathfrak{p}=(p)$ be a principal ideal generated by a rational prime number p. A ...
5
votes
1answer
75 views

How prove can't exist a set $A$ of positive integers satisfying the two conditions

Question: Show that there can't exist a set $A$ of positive integers such that the following two condition hold: (1) For every integer $m>1$, there exist $a,b\in A$ such $a+b=m$. (2) ...
4
votes
3answers
53 views

How would you show that the Riemann Zeta function, $\zeta(s) < 0$ for $s \in (0,1)$?

How would you show that the Riemann Zeta function, $\zeta(s) < 0$ for $s \in (0,1)$? So far I have that along the critical strip \begin{align} \zeta(s) &= ...
0
votes
1answer
23 views

Probability of highest common factor in Williams

In David Williams' Probability with Martingales, $\exists$ this exercise. Let s > 1 and let $\zeta(s) = \sum_{n=1}^{\infty} {n^{-s}}$. Let X and Y be independent $\mathbb{N}$-valued random variables ...
1
vote
1answer
39 views

What does “generate freely” mean?

Given a number field $K$ (i.e. $\mathbb Q\le\ K\le\mathbb C$, $[K:\mathbb Q]=n$), the relative number ring is $R=\mathbb A\cap K$, where $\mathbb A$ is the ring of the algebraic integers in $\mathbb ...
2
votes
1answer
51 views

Continued fraction expansion of Pi (oeis A001203). [duplicate]

I would like to understand how you get the numbers $$3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+...}}}}$$ i.e. $\{3,7,15,1,292,...\}$ (A001203). In the comments of A046965 is explained a method ...
1
vote
0answers
44 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
6
votes
4answers
146 views

When does $V/\operatorname{ker}(\phi)\simeq\phi(V)$ imply $V\simeq\operatorname{ker}(\phi)\oplus\phi(V)$?

When does $V/\operatorname{ker}(\phi)\simeq\phi(V)$ imply $V\simeq\operatorname{ker}(\phi)\oplus\phi(V)$? I wrote it down in an imprecise way on purpose. The notation above is the linear algebra one: ...
0
votes
0answers
29 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
0
votes
0answers
34 views

If $f(d)$ is multiplicative, then show that $F(n) = \sum_{d|n} (f(d))^k$ is also multiplicative

If $f(d)$ is multiplicative, then show that $ F(n) = \sum_{d|n} (f(d))^k$ is also multiplicative $n \ge 1$ is a positive integer $d$ is a positive divisor of $n$ $k \ge 1 $ is an integer My try ...
0
votes
0answers
19 views

There exists only a finite number of ideal classes in a number ring

Let $K$ be a number field (i.e. $\mathbb Q\le K\le\mathbb C$ s.t. $[K:\mathbb Q]=n$) and $R=\mathbb A\cap K$ the relative number ring. Calling $\Phi(R)$ the set of ideals of $R$, we define on it the ...
2
votes
1answer
53 views

A Quadratic Diophantine equation in three variables

Can the following Diophantine equation be solved for all solutions? $$x^2 + yz = 2$$ Then get a closed expression for $x_n, y_n, z_n$. It may be related to primes. I'll explain further how I got ...
-2
votes
0answers
47 views

Count Triangular Triplets [on hold]

Given a range [L,R] we need to calculate numbers of such triplets [A,B,K] which follows A+B=K where A,B are any two triangular numbers and K must be in an ...
0
votes
0answers
92 views

How prove this there exists $\varepsilon\in(0,\dfrac{1}{2014})$, such for any positive real numbers $a_{1},a_{2},\cdots,a_{n}$ [on hold]

Question: Give the positive integer number $n$, show that: there exists $\varepsilon\in(0,\dfrac{1}{2014})$, such for any positive real numbers $a_{1},a_{2},\cdots,a_{n}$, there exist positive $u$, ...
0
votes
1answer
60 views

Solve $i^3j-j^3i=x^3y-y^3x$

Do anyone have an idea about how to solve this kind of equation: $i^3j-j^3i=x^3y-y^3x$ where $i,j,x,y$ are distinct natural numbers and $i>j$ and $x>y$ Regards
-3
votes
0answers
26 views

Maths: Profit and Lose. [on hold]

A temple has 100 thousand visitors every Friday & the statistics shows that for every 3 new visitors, there are 2 regular visitors. The shop in the temple recruits consultant to increase the ...
2
votes
0answers
21 views

Number of nonnegative solutions of linear diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
1
vote
0answers
45 views

Could any one explain the difference between the theorems?

In the paper http://annals.math.princeton.edu/2007/165-2/p04 Theorem 2. Let $b \ge 2$ be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a finite automaton. ...