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

learn more… | top users | synonyms (2)

0
votes
0answers
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 ...
1
vote
1answer
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, ...
4
votes
2answers
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 ...
3
votes
1answer
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 ...
6
votes
0answers
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 ...
-3
votes
1answer
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$ ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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)$?
10
votes
2answers
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 ...
1
vote
1answer
17 views

Prove that $a(x)$ divides $(v(x) - t(x))$

"Let $a(x), b(x) \in \mathbb{R}[x]$, not both the zero polynomial and suppose that gcd[$a(x), b(x)$] = 1. Let $u(x), v(x) \in \mathbb{R}[x]$ be such that $a(x)u(x) + b(x)v(x) = 1$ Let also $s(x)t(x) ...
0
votes
2answers
16 views

Prove that $q(x)$ does not divide $p_k(x)$

Let $n \in \mathbb{N}$ and let $p_1(x), p_2(x), ... *p_n(x)$ be $n$ irreducible polynomials over $\mathbb{R}$. Define the polynomial $p(x) = p_1(x) * p_2(x) *... *p_n(x) + 1 $ where 1 is the constant ...
1
vote
1answer
50 views

Why does this method for finding the number of factors for number X not work?

As you may know, in order to find the number of factors for natural number X, we take the prime factorization, add one to each exponent, and multiply, as such. $...
5
votes
1answer
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 ...
2
votes
1answer
114 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
0
votes
0answers
31 views

Prime factors polynomials

I have proved a theorem which I will state: For $f(x)=x^n+\sum_{i=1}^nh_ix^{n-i}$ a polynomial of degree $n$ where $h_i=r_i+d_i$ with $r_i$ real and $d_i$ infinitesimal. Then if $x^n+\sum_{i=1}^nr_ix^{...
2
votes
4answers
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?
2
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
3answers
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 ...
1
vote
0answers
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 ...
2
votes
2answers
64 views

What is the Least Prime Factor of $3^{3241} + 8^{2433}$

I'm not sure how to do this question Attempt $$3^{3241} + 8^{2433}$$ I start by taking this number mod 3 $$3^{3241} + 8^{2433} \equiv 8^{2433} \mod 3$$ No we can see that $8^2 \equiv 1 \mod 3$. So $$...
1
vote
1answer
20 views

Best known inequality for the larger prime number of a product?

We all know given two prime number's $b$ and $a$ whose product is $c$: $$ c \geq b \geq \sqrt c \geq a \geq 2 $$ where, $ab=c$ I was wondering if the inequality for $b$ could be improved upon ...
1
vote
0answers
24 views

Analog of Euler's Factorization method

One of Euler's discoveries was if an integer $n$ can be represented as a sum of two squares in two distinct ways, then one can factor $n$ explicitly. Of course, the method was ineffective as an ...
12
votes
0answers
181 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
2
votes
2answers
107 views

Numbers $m = pq^4$ ($p,q$ are distinct primes) for which $m$ divided by the number of its factors is an integer

The $\operatorname{Ionof}$ (Integer on number of factors) of an integer is the integer divided by the number of factors it has. For example, $18$ has $6$ factors so $\operatorname{Ionof}(18) = \frac{...
1
vote
1answer
30 views

Proving that if gcd(m, n) = 1, and if d divides mn, then there exist unique numbers a and b such that a divides m, b divides n, and d = ab.

What do I know? If d | mn, there exist an integer k such that dk = mn. I also know that because gcd(m, n) = 1 there exist some integers x and y such that mx + ny = 1. I am having trouble to prove ...
0
votes
0answers
14 views

On factoring given $PQ-1$ has small factors.

Suppose we have an RSA number $PQ$ where $PQ-1$ has small factors. Will this give any advantage to factor $PQ$?
2
votes
3answers
194 views

Find the number of even factors of 126000

What is an easy way to solve the problem? I can solve it by trying all possible even numbers, but I don't think it is a smart way. Find the number of even factors of 126000.
4
votes
1answer
38 views

On factoring and integer given the value of its Euler's totient function.

In an entrance test for admission into an undergraduate course in mathematics the following question was asked. Consider the number $110179$ this number can be expressed as a product of two distinct ...
1
vote
0answers
8 views

$\gcd({p_1}^{n_1},{p_2}^{n_2})$ associates with $1$ if $p_1,p_2$ are prime and do not associate

$R$ is a integral domain, $p_1$ and $p_2$ are prime, $p_1$ and $p_2$ do not associate, $n_1,n_2 \ge 1,n_1,n_2 \in \mathbb N $, I need to show that $g:=\gcd({p_1}^{n_1},{p_2}^{n_2})$ associates with $1$...
0
votes
0answers
22 views

best way to find sum of powers of prime factors of a number

What is the best way to find the sum of powers of prime factors of a number? What I did till now is : ...
4
votes
1answer
64 views

Sequence generated by $2^k-1$ contains new prime factors

I was playing around with the sequence where the $k^{th}$ number is equal to $2^k-1$. It seems that all numbers except $63$ contain at least one new prime in there prime factorization. That is a prime ...
3
votes
2answers
56 views

Factoring the factorials

Just for the fun of it, I've started factoring $n!$ into its prime divisors, and this is what I got for $2\leq n\leq20$: $$\begin{align} 2! &= 2^\color{red}{1} &S_e=1\\ 3! &= 2^\color{red}...
0
votes
0answers
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 , ...
2
votes
1answer
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 ...
0
votes
1answer
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{...
7
votes
0answers
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 ...
0
votes
2answers
28 views

Let $n = 2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d \nmid n$

Let $n=2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d$ does not divide $n$. My attempt $n^2 = 2^{62} * 3^{38}$ Total divisors $= 1 + 62 + 38 + 62*...
1
vote
1answer
68 views

Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
0
votes
1answer
25 views

Pollard's $p-1$ method

I've been reading some notes regarding the Pollard's $p-1$ method1 and I came across an aglorithm that (from the math standpoint) I don't fully understand: Given that $\textbf{a = 2}$ and also in my ...
0
votes
1answer
26 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
0
votes
1answer
15 views

Significance of derivative in finding square free decomposition

If $gcd(f(x),`f(x))=1$ then f(x) is square free. But what is the reason behind taking derivative of f(x)? How one came to this conclusion?
0
votes
0answers
28 views

Is this algorithm for testing whether or not an integer is prime correct?

Suppose I want to determine whether or not integer $p$ is prime. I create a cycle graph with $p$ vertices ($C_p$). I take the edge-complement of this graph, which will be the complete graph ($K_p$) ...
2
votes
0answers
46 views

A question on polynomials.

Let a polynomial $f\in\mathbb{R}[x,y]$, and $f(x,y)=(x^2+y^2)p(x,y)^2-q(x,y)^2$ and $p,q$ are coprime to each other. When do, $f$ and $\frac{{\partial f}}{{\partial x}}$ and $\frac{{\partial f}}{{\...
1
vote
2answers
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) ...
2
votes
1answer
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? ...
0
votes
0answers
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}[\...