# Tagged Questions

For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.

17 views

### How accurate is the approximation of the number of rough numbers?

A number is called a $y$-rough number, if it has no prime divisor below $y$. The number of rough numbers in an interval, lets say, $[10^{99},10^{100}]$ is approximately the length of the interval ...
55 views

### Strange results in mersenne.org database

I am interested in GIMPS project. I was browsing through known Mersenne prime numbers when I discovered strange records in their database. For example, M6972593 is the 38th Mersenne prime. However, ...
121 views

### Matrix decomposition into square positive integer matrices

This is an attempt at an analogy with prime numbers. Let's consider only square matrices with positive integer entries. Which of them are 'prime' and how to decompose such a matrix in general? To ...
68 views

### Does a sequence based on hereditary factorisation always terminate?

The well-known Goodstein sequences are based on the hereditary base-$b$ notation, where you don't just present the digits in base $b$, but also the corresponding exponents etc. That lead me to the ...
61 views

### The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
30 views

### Here is a break-down graph of operations done in 4-bit integer multiplication.

The blue nodes represent the number $b = b_3b_2b_1b_0$, and the green nodes represent the number $a = a_3a_2a_1a_0$. The yellow nodes are the output bits after multiplying $a \cdot b$. If $a\cdot b$ ...
19 views

### Discrete Logarithm vs Integer Factorization

Can anyone please tell me if finding discrete logarithm is considered more difficult than integer factorization? We have very advanced methods to find factors of large composite numbers like Number ...
63 views

### Numbers $a$ such that if $a \mid b^2$ then $a \mid b$

I want to describe the set of numbers $a$ such that if $a \mid b^2$ then $a | b$ for all positive integers b using the prime factorizations of $a$ and $b$. What would be a good way to approach this ...
66 views

### Prove That $n(n+1)$ Can Never Be a Square Number by Showing the Atleast One of Exponents in the Prime Power Decomposition Isn't Even

Can someone show me how to prove that when $n>0$, $n(n+1)$ can never be a square number by demonstrating at least one of the exponents in the prime power decomposition is not even? Here's what I ...
13 views

### Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
18 views

### What is the difference between common components of $f(x,y)$ and common factor of $f(x,y)$?

Let $f(x,y)$ be a polynomial.What is the difference between common components of $f(x,y)$ and common factor of $f(x,y)$?
109 views

### Can one factor matrices?

I know that one can factor integers as a product of prime numbers. Is there an analog of it to matrices? Can we define prime matrices such that every matrix is a product of prime matrices? Is there ...
17 views

42 views

### When is the norm of a number even?

In the ring $$\textbf{Z}[i],$$ if the norm of an element is divisible by $2$, then the element must be divisible by $$1 + i,$$ and vice versa. A similar result holds for $$\textbf{Z}[\sqrt 3]$$ and ...
114 views

158 views

### Solutions to a quadratic diophantine equation $x^2 + xy + y^2 = 3r^2$.

Let $k,i,r \in\Bbb Z$, $r$ constant. How to compute the number of solutions to $3(k^2+ki+i^2)=r^2$, perhaps by generating all of them?
73 views

### Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
36 views

### Modified Sum of Products

A given number k is to be expressed as a sum of products of integers keeping in mind that the integers used in above process do not exceed their cumulative sum as 100. For e.g., k = 19 can be ...
61 views

### What is the sum of the prime factors of $2^{16}-1$?

I know $2^{10}=1024$ and $2^6=64$, but it seems they are not very helpful in solving this problem. There must be a trick to solve the problem in an easy way. What is the sum of the prime factors ...
34 views

### Prove by contradiction that : There are Infinite Primes. [closed]

Specify $P$, ~$P$,Q and ~$Q$; For this proof I am having difficulty understanding what p and q signify. I was reading Euclid proof http://www.math.utah.edu/~pa/math/q2.html . But I do not quite ...
64 views

68 views

### What are the prime factors of $4^{256}+253\$?

I search a composite number near $4^{4^4}$ with a very large smallest prime factor. A candidate is $$4^{4^4}+253=4^{256}+253$$ The number is composite and has $155$ digits, so it is in the range , ...
56 views

### Large Prime numbers

Say we have $2^{690} + 345^4$ and we want to figure out whether this is a prime number. I feel that we could break down the numbers into their respective prime factors (prime factorization) and use ...
49 views

### Use Fermat factorization to factor $809009\ldots$

Use Fermat factorization to factor $809009\ldots$ So far I have: \begin{align} \sqrt{809009} & = 889.449 \\ & = 890 \\[6pt] \sqrt{890^2 - 809009} & = 130\ldots ∉ \mathbb Z \\[6pt] \sqrt{...
83 views

### Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
28 views

54 views

### Proving the set of prime numbers in $\mathbb{Z+}$ is infinite

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them) ...
33 views

### Why are primes of the form p^2 - 2 for prime p seemingly unusually likely to be factors of prime-exponent Mersenne numbers?

The sequence A049002 (primes of form $q^2 - 2$, where $q$ is prime) appears to contain a high proportion of elements that are factors of prime-exponent Mersenne numbers (see below). I wonder why? ...
28 views

### Prime Decomposition of an ideal in a number field.

I have been stuck on the 26th problem of the 3rd chapter from Marcus' Number Fields. Let $\alpha=\sqrt[3]{m}$ where $m$ is a cubefree integer, $K=\mathbb{Q}[\alpha]$, \$R=\mathbb{A} \cap \mathbb{Q}[\...