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)

2
votes
2answers
41 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) = ...
0
votes
1answer
25 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
12 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
188 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
34 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 ...
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
59 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 ...
2
votes
2answers
48 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! &= ...
0
votes
0answers
64 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
54 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
47 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] ...
7
votes
0answers
76 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
27 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 + ...
1
vote
1answer
67 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
14 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
25 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
34 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 ...
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
24 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
26 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 ...
0
votes
0answers
49 views

Why does this equation has not any solution?

Suppose $P(x,y)$ and $Q(x,y)$ are polynomials, and $P,Q$ are coprime. Why does the equation $${\left( {\frac{{xP + {{\left( {\frac{Q}{P}} \right)}^2}{P_x}}}{{yP + {{\left( {\frac{Q}{P}} ...
1
vote
0answers
14 views

Integer Logic - Prime and Unique Factorization Proof

I could use some help with this problem: Let a, b ∈ Z (integer set) such that (a, b) = 1. Suppose that ab = $x^2$ for some x in Z (integer set). Prove that a = $y^2$ and b = $z^2$ for some y ...
3
votes
2answers
35 views

Proof of (n) and (n+1) Sharing No Prime Factors

A number $(n)$ has a set of prime factors $\{\alpha_1, \alpha_2,...\alpha_\epsilon\}$ and a number $(n+1)$ has a set of prime factors $\{\beta_1,\beta_2,...\beta_\psi\}$. The conjunction, ...
0
votes
0answers
24 views

Factorising into Gaussian primes $4+3i$

I want to find the Gaussian prime factors of $(4+3i)$ $$(4+3i)(4-3i) = 25=5^2$$ $$5: (2-i)(2+i)$$ so $$(4+3i)(4-3i) = 25=5^2 = (2-i)(2+i)(2-i)(2+i)$$ That was my answer but the solution says: ...
3
votes
3answers
37 views

Proof that $\sum_{d|m} |\mu(d)|=2^n$, where $n$ is the number of distinct prime divisors of $m$?

Given an integer $m$ such that $n$ is denoting the distinct prime divisors of $m$, is there a proof that the sum over the divisors of m of the absolute value of the Möbius function $\mu(d)$ is equal ...
1
vote
3answers
32 views

How to prove that the g.c.d is equal to the prime factorization raised to the minimum of two powers

for the prime factorization of $a$ and $b$ as $$a = p_1^{\alpha_1}p_2^{\alpha_2}\cdots{p_t}^{\alpha_t}$$ and $$b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_s^{\beta_s}.$$ I want to prove that $d = (a,b)$ ...
1
vote
1answer
50 views

How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?

Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq n$ and $\gcd (m, n) = 1$? Note that $\gcd (m, n)$ is the greatest common divisor of $m$ and ...
0
votes
0answers
18 views

Exponent of x in the prime factorization of y?

This is a simple one. I recently came across the following phrase: "$(x)_y =$ the exponent of $p_y$ in the prime factorization of $x$, for some $x, y<0$" I know what prime factorization is, and ...
0
votes
0answers
25 views

Properties involving prime factorization and divisibility

Can anyone help me out this with proof? Let n be a positive integer greater than 1 with the property that whenever n divides a product ab where a,b ∈ Z, then n divides a or n divides b. Prove ...
3
votes
1answer
20 views

Prime and Unique Factorization Proof

I could use some help with this question here: Let $n ∈ Z, n > 1$. Prove that if n is not divisible by any prime number less than or equal to $√n$, then n is a prime number. Here I assumed ...
2
votes
4answers
110 views

$2^{61}$ as a multiple of 3… is that possible?

I had a recent conversation with a friend of mine who said that $2^{61}$ was a multiple of 3, but I wanted to disprove this argument by claiming that all values of $2^n$ were not a multiple of 3 at ...
2
votes
1answer
52 views

Algebraic number theory, Marcus, Chapter 3, Question 9

Question 9 in Marcus book. Let $K$ and $L$ be the number field such that $K\subset L$ and let $R,S$ be their algebraic integers, respectively. a) Let $I$ and $J$ be ideals in $R$, and suppose ...
6
votes
5answers
1k views

What's problematic about finding out if a large number is Prime or not?

I was reading somewhere that it's hard to determine if a number is prime or not if it gets too large. If I understand correctly, all numbers can be broken into prime factors. And numbers which can't ...
1
vote
1answer
63 views

Sum of all numbers less than equal to X relatively prime to all number less than Y

Here's a programming question probably needing lots of math: Given two integers X and Y, you need to find the sum of all positive integers less than or equal to X, which have no divisor smaller ...
2
votes
0answers
37 views

A very nice pattern involving prime factorization

A while ago I was fiddling around with prime numbers and C++. I defined: $$f_a(b)= \text{ the amount of numbers } 2^a\leq n<2^{a+1}\text{ with } b \text{ prime factors}$$ I calculated $f_a(b)$ for ...
0
votes
2answers
24 views

Calculating the difference of the factors of a semiprime

Let there be a semiprime $N=p q$ where $p$ and $q$ are prime numbers. If the value of $N$ is given, is there any way to calculate the value of $(p-q)$. If not exactly then approximately ? Update : ...
0
votes
1answer
42 views

Finding the $18$th cyclotomic polynomial $\phi_{18}(X))$.

I know that for an $n$th cyclotomic polynomial $\phi_n(X)$ the following equations hold: $x^n-1=\prod_{n_1|n} \phi_{n_1}(X)$ For $n=p$ prime, $\phi_p(X)=X^{p-1}+...+X+1$ So I used the following ...
8
votes
2answers
111 views

Is $every$ prime factor of $\frac{n^{163}-1}{n-1}$ either $163$ or $1\;\text{mod}\;163$?

This was inspired by this question. More generally, given prime $p$ and any integer $n>1$, define, $$F(n) = \frac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+\dots+1$$ Q: Is every prime factor of $F(n)$ ...
5
votes
0answers
58 views

Largest prime known to ancients

As is well known, Fermat couldn't check the primality of $F_{5} = 2^{2^{5}} + 1$. This raises an interesting question : what was the largest prime number that was known to ancients (particularly ...
0
votes
1answer
28 views

Square Root of Rational Number $\frac{A}{B}$

Here's the question: Let $x=\frac{A}{B}$ be a positive rational number in lowers terms (i.e., $A, B\in\mathbb{N}$ and $hcf(A,B)=1$). Prove that $\sqrt{x}$ is rational if and only if $A$ and $B$ are ...
7
votes
1answer
176 views

Uniqueness or non uniqueness of a pair of natural numbers

Let $1<m<n$ be two natural numbers. Let us call $(m,n)$ a math.se pair if the prime factors of $m$ are the same as those of $n$ and the prime factors of $m+1$ are the same as those of $n+1$, ...
9
votes
9answers
2k views

The lowest number that is a multiple of both 60 and the integer n is 180. Find the smallest possible value of n.

I have one solution but I think it's just a wild guessed one. Tell me if I am correct and also if not, then how should it be done? What I have done is divided 180 by 60 to get 3. Then take lcm of 60 ...
1
vote
1answer
28 views

Prime factorization of a large integer. Prove $A − \sqrt{N} < 1$ , given $N = pq$, $A =\frac{p+q}{2}$ and $|p − q| < 2 \sqrt[4]{N}$.

Prove $A >\sqrt{N}$ and $A − \sqrt{N} < 1$, given that $|p − q| < 2 \sqrt[4]{N}$ and $A =\frac{p+q}{2}$, where $p$ and $q$ are primes, N is a large integer and $N = pq$. By $(p+q)^{2} ...
10
votes
3answers
207 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
1
vote
1answer
35 views

Factorization of Euler totient function

We know that if $~n = p_{1}^{a_1} \cdots p_{s} ^ {a_s}~$ then $~\phi(n) = p_1^{a_1 - 1}(p_1 - 1)\cdots p_s^{a_s - 1} (p_s - 1)$. If $~q~$ is prime dividing $~\phi(n)~$ then there are two ...
4
votes
2answers
101 views

Unable to find solution for $a^2+b^2-ab$, given $a^2+b^2-ab$ is a prime number of form $3x+1$

I have a list of prime numbers which can be expressed in the form of $3x+1$. One such prime of form $3x+1$ satisfies the expression: $a^2+b^2-ab$. Now I am having list of prime numbers of form $3x+1$ ...
0
votes
2answers
56 views

Prove that $7^{\frac 14}$ is not rational using the Unique Factorization Theorem.

I am currently trying to prove this using the Unique Factorization Theorem and I am stuck. I attempt to prove this BWOC and assume $7^{\frac 14}$ is rational so that it can be expressed as $\frac ...