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
16 views

Proof: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes.

Let $x=(n+1)!+2$. I get how to prove that $x$ or $x+1$ is prime, but there is a step in my book that proves that $x+i$ is prime like this: $x+i=(1)(2)(3)(4)....(n+1)+(i+2)$. But then it factors out ...
1
vote
1answer
43 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
3
votes
3answers
74 views

For what numbers $n$ is $\sqrt{n}$ irrational?

I would say it has something to do with the numbers that can be expressed as a factor of different prime numbers, but when I get to $8$, that can be changed to $2^3$, which goes against this. Is there ...
1
vote
0answers
24 views

How long does the General Number Field Sieve actually take?

According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer. Using the complexity equation for the General Number Field Sieve with ...
0
votes
2answers
16 views

asymptotic and monotonically increasing properties of prime factorization function?

Questions We define $A(x)= \text{number of prime factors of x}$ For example $A(2 \times 3^2) = 3$ I noticed when $s_k = \frac{N!}{\prod_j n_j}$ and $\sum_{j} n_j = N$ $$ s_1 < s_2 \implies ...
0
votes
1answer
20 views

Number of positive integral divisors

I understand in order to find number of divisors, you need to follow following method, But I don't seem to find why it works. In order to find number of divisors a number has, you find the prime ...
0
votes
1answer
40 views

Proving the primality of these large numbers?

In 2007, Vautier claimed that the largest known consecutive pair of prime numbers (at the time) was $2003663613\cdot2^{195000}-1$ and $2003663613\cdot2^{195000}+1$. I was wondering how Vautier found ...
3
votes
0answers
33 views

Distinct prime factorization function formulation to find mobius function?

Background I recently noticed the following: $$ S(x)=\sum_{r=1}^\infty x^{p_r} $$ where $p_r$ is the $r$'th prime: $$ \sum_{r=1}^\infty S(x^r) = \sum_{r=1}^\infty \frac{x^{p_r}}{(1-x^{p_r})} $$ ...
2
votes
1answer
72 views

How does one prove that $2\uparrow\uparrow16+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: ...
-1
votes
1answer
40 views

Find all $a$, so $q$ prime number which ,$q\times n= aaaaaaa$ [duplicate]

I need your helping to find all the $a$ numbers,which follow the next rules: there is prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $a$. ...
4
votes
0answers
62 views

What is the smallest prime factor of the number $14^{14^{14}}+13\ $?

What is the smallest prime factor of the number $$N\ :=\ 14^{14^{14}}+13\ ?$$ The number of digits of $N$ is $12,735,782,555,419,983$ (The number of digits of $N$ has itself $17$ digits). The first ...
0
votes
2answers
65 views

Prove that there is prime number and natural so $n\times q$ digits are $1$.

I need your helping to prove that there is a prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $1$. for example:if $n=3$ then $3\times 37=111$ ...
0
votes
2answers
31 views

RSA Encryption Original Primes $p$ and $q$

I am well aware of the math behind the RSA encryption system, and why it works. The bank, for example, publishes a pair of numbers $(e,n)$ which are used for encryption by the customers. The bank then ...
2
votes
1answer
41 views

Density of numbers with exactly $n$ distinct prime factors in $\mathbb{N}$

It is quite well known that the density of the primes in $\mathbb{N}$ is $0$, that is, $$\lim_{n\to\infty}\frac{|\{p\mid p\leq n, p \text{ prime}\}|}{|\mathbb{N}_{\leq n}|}=0$$ It is less well-known, ...
0
votes
4answers
54 views

Prove that for every number that's not a prime, it exists a prime $p$ with $p\mid n$ and $p \leq \sqrt{n}$

For $n \in \mathbb{N}$, if $n$ is not a prime and $n ≥ 2$, it exists a prime $p$ with $p\mid n$ and $p \leq \sqrt{n}$. How would I mathematically correctly prove this sentence? I've thought about ...
3
votes
1answer
124 views

Who knows further prime factors of $3^{3^3}+4^{4^4}=3^{27}+4^{256}\ $?

The partial prime factorization of $$3^{3^3}+4^{4^4}=3^{27}+4^{256}$$ is $$43\times 691\times C150$$ , where C150 = ...
0
votes
1answer
50 views

Unique prime factorization [duplicate]

We all know that $$15=3 \times 5$$ And $$15 =(-3) \times(-5)$$ Since $3 \neq -3$ and $5 \neq -5$ , we have two different prime factorizations ! Is this wrong ? If this is wrong , then there are ...
3
votes
1answer
44 views

A smart way to do this question.

Let $S=\{0,1,2,\dotsc,25\}$ And $T=\{n\in S : n^2+3n+2\text{ is divisible by }6\}$ Then the number of elements in $T$ is? One way I know is to factorise it as $(n+1)(n+2)$. And then put each $n$ ...
10
votes
3answers
165 views

Prove that $\frac{2^{122}+1}{5}$ is a composite number

As in the title. It's very easy to show that $5|2^{122}+1$, but what should I do next to show that $\frac{2^{122}+1}{5}$ is a composite number? I'm looking for hints.
0
votes
1answer
24 views

the associate of a prime is prime in integral domain

I was hoping someone could give me a hand getting started trying to prove that in an integral domain, if a and b are associates, then a is prime if and only if b is.
2
votes
3answers
36 views

Finding the prime number $n$: why checking for a divisor between 2 and $\lfloor \frac{n}{2} \rfloor$ is enough?

Let's say I want to check whether 33 (say $n$) is a prime number or not. Instead of checking whether 33 is divisible by a number between 2 and 31 or not, it is sufficient enough to verify that 33 is ...
-1
votes
0answers
44 views

What is an upper bound for number of semiprimes in the interval $[n^2,n^2+2n]$

A semi prime is a number which is product of two distinct primes. What is an upper bound for number of semi primes in the interval $[n^2,n^2+2n]$?
0
votes
1answer
42 views

Is every polynomial with integer coefficients prime in $\mathbb{Z}[x]$ also prime in $\mathbb{Q}[x]$? [closed]

The question is as in the title: Is every polynomial with integer coefficients prime in $\mathbb{Z}[x]$ also prime in $\mathbb{Q}[x]$?
2
votes
1answer
40 views

What is an upper bound for number of semiprimes less than n?

A semi prime is a number which is product of two distinct prime number. What is an upper bound for number of numbers in the form pq less than n? $p,q$ are prime numbers smaller than $n$.
1
vote
2answers
19 views

Mysterius semiprime fact in other number bases

So you have a semiprime n n = p*q where p < q A curious fact about bases is that if a number x ends with a zero in base y, then x is divisible by y. Therefor, if we where to represent n in all ...
2
votes
0answers
149 views

Factoring semi-primes, convert algorithm to function [closed]

I found an interesting method of factoring semi-primes when I been searching for ways to predict the mod result of given number. The algorithm This algorithm is ...
3
votes
0answers
19 views

Product of the Euler phi function [duplicate]

Prove the following statement: If $n, m\in\mathbb{Z} $ and $g=$gcd$(n, m) $ then is $$\varphi(m, n) =\frac{ \varphi(m) \varphi(n) g} {\varphi(g)}. $$ Hint: Prove the statement with induction above ...
2
votes
1answer
27 views

Is it correct? Prove that any fraction can be reduced

I want to know if my prove is correct. My goal is proving: Hypothesis: $a,b \in \mathbb Z$ and $a,b \notin \{-1, 0, 1\}$. Thesis: for all $ a, b$, exist $a',b'\in \mathbb Z$ that verify ...
5
votes
0answers
29 views

What would be some winning strategies for a prime factorization lottery?

With the hysteria surrounding the Powerball jackpot, I'm sure a lot of you have been thinking about the tiny odds of a lottery in which you have to match five or six numbers out of a small set (like 1 ...
1
vote
5answers
56 views

Why is the product of two consecutive integers $n \cdot( n+1) \forall n > 2$ guaranteed to have at least two prime factors?

I was reading this paper: http://fermatslibrary.com/s/a-new-proof-of-euclids-theorem and became confused when reading this line: Since $n$ and $n + 1$ are consecutive integers, they must be ...
1
vote
3answers
60 views

If n is positive integer, prove that the prime factorization of $2^{2n}\times 3^n - 1$ contains $11$ as one of the prime factors

I have: $2^{2n} \cdot 3^{n} - 1 = (2^2 \cdot 3)^n - 1 = 12^n - 1$. I know every positive integer is a product of primes, so that, $$12^n - 1 = p_1 \cdot p_2 \cdot \dots \cdot p_r. $$ Also, any idea ...
2
votes
1answer
31 views

Factorization of ideal in field $\mathbb{Q}(\sqrt[3]{2})$ and its normal closure

So far I've worked only with quadratic fields, and I'm not sure how to work with 3rd roots. I have ideal $(5)$ and need to factor it in $\mathbb{Q}(\sqrt[3]{2})$ and its normal closure. I know that ...
5
votes
1answer
42 views

Number of the form $2^i3^j5^k$ closest to a given number $n$

How do I find a number of the form $2^i3^j5^k$ closest to a given number $n$, with $i, j, k \in \mathbb{N}$ numerically? Of course, I could try $\lfloor \log_2{n}\rfloor \times ...
1
vote
1answer
38 views

Calculating $n$ mod $m$ given the prime factorization of $n$

Say I have the prime factorization of a large integer $n$. $$n=p_1^{a_{1}}\cdot p_2^{a_{2}}\ldots p_k^{a_{k}}$$ However, I do not have $n$ itself. How do I calculate $n$ mod $m$, given only $n$'s ...
0
votes
1answer
27 views

Proof that there exists a larger prime than prime number P, which is the largest of a finite set of primes?

I am currently working on a problem in which I must prove that there exists a larger number prime number than prime $P$, the largest prime of a finite set. Here are a list of considerations: There ...
0
votes
2answers
42 views

How many sets of 8 3-digit consecutive even numbers are possible such that product when divided by 5 gives perfect cube?

The sum of eight three-digit consecutive even number is S.When S is divided by 5, it results in a perfect cube.How many sets of such eight numbers are possible?
0
votes
1answer
26 views

How to find product of factors of a number if the factors are perfect square?

Let M be the set of all the distinct factors of the number N = 6^5 * 5^2 * 10, which are perfect squares. Find the product of the elements contained in the set M. N = 2^6 * 3^5 * 5^3 Even power of ...
1
vote
2answers
38 views

Sum and product of greatest prime factors

Consider this functions below. $$f(n)=\sum_{k=2}^{n}gpf(k)$$ $$g(n)=\prod_{2}^{n}gpf(k)$$ where $gpf$ is the greatest prime factor function.(For example, $gpf(30)=5$) Is it possible to find an ...
1
vote
2answers
30 views

Is there list of composite Mersenne numbers with their factorization?

Here is a list of known Mersenne primes. http://mathworld.wolfram.com/news/2009-06-07/mersenne-47/ I'm looking for a list of composite Mersenne numbers(when $p$ is prime $2^p-1$ isn't) with their ...
2
votes
2answers
38 views

Prove that $\sigma(n)\le \lceil\log_2(n)\rceil$

Let $f:\mathbb{N}\to\mathbb{N}$ be defined as $f(1)=1$ and if $n=\prod_{r=1}^{k}p_r^{\alpha_r}$ is the prime decomposition of $n$ then: $$ f\left(n\right)=\prod_{r=1}^{k}(p_r-1)^{\alpha_r} $$ Let ...
2
votes
1answer
32 views

Knowing which factorization algorithm to use

There are many ways of factorization available, e.g. trial division, Pollard rho, elliptic curve factorisation, the general number field sieve. But for what ranges of numbers are such algorithms ...
2
votes
2answers
55 views

Use congruences to factor $n=87463$ (Fermat's Factorization?)

I'm studying for my number theory test tomorrow, and these are the last questions in my study guide. I think I understand Fermat's factorization, however, I can't tell how my professor wants us to ...
5
votes
5answers
713 views

Prime factors of a factorial [closed]

Determine all (distinct) prime factors of $1000!$. Here we seek a description of these factors as a set; there is no need to compute them. What exactly do I need to determine here?
2
votes
2answers
49 views

Suppose $n|a^2-1$ Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$

Suppose $n|a^2-1$ where $a>1$ and n is odd. Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$. Part 2 Show that if $a<n-1$ then this gives a nontrivial factorization of n What I did: I found the ...
8
votes
1answer
60 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
0
votes
0answers
30 views

Is the root of all numbers who have a lone prime factor irrational?

I've got what I think is a proof, am wondering if I've made a mistake. Proof by contradiction: Suppose $\sqrt{n}=a/b$, with $a$ and $b$ being integers and coprime meaning $a/b$ is rational. Square ...
2
votes
2answers
71 views

Find 4 positive integers not exceeding 70,000 such that each have more than 100 divisors

I am looking at problems in Vandendriessche and Lee's Problems in elementary number theory and this is one of their problems: Find $4$ positive integers not exceeding $70000$ such that each have ...
2
votes
5answers
68 views

Find the value of $abc$.

The product of two $3$-digit numbers with digits $abc$, and $cba$ is $396396$, where $a > c$. Find the value of $abc$. In order to solve this, should I just find the prime factorization of ...
3
votes
2answers
37 views

Gaussian prime factorization.

I have a hard time on factorizing elements from $\mathbb{Z}[i]$, especially $-19+43i$. I know that the primes in $\mathbb{Z}[i]$ are: $1+i$. $p$ from $\mathbb{N}$, $p=4k+3$ , $k$ integer ( $p\equiv ...
1
vote
1answer
49 views

Find polynomial to use for prime ideal factorization

L.S., In an exercise for my algebraic number theory homework I came across the following problem: I would like to factor ideals $(2)$ and $(7)$ in $K = \mathbb{Q}(i, \sqrt{14})$. I managed to show ...