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)

1
vote
1answer
35 views

A non-UFD where prime=irreducible [duplicate]

It is easy to see that in an atomic domain (where every element factors into irreducibles), we have that all irreducibles are prime iff the domain in question is an UFD. I think it is not true for a ...
4
votes
2answers
284 views

Contradiction on prime decomposition

Take $n = 12$ $12$'s prime factorization is $2^1\times2^1\times3^1$ So then, the number of factors by UFT is $(1+1)(1+1)(1+1) = 8$ But there's only $1,2,3,4,6,12 = 6$ factors!! Where are the other ...
2
votes
1answer
26 views

Find sum of possible pairs for given LCM and GCD

I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$ For $A=72$, $B=3$ Possible pairs will be - $(3,72)$, ...
1
vote
0answers
34 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
3
votes
3answers
33 views

Proving that a number has at least 3 distinct prime factors.

Let abc be a 3-digit natural number (written in base 10). Prove that the 6-digit number abcabc has at least three distinct prime factors. I know that to prove that the 6-digit number has at ...
1
vote
2answers
58 views

Factorizing $88^2-12^2$

I tried finding the square root of both sides but it is in decimal and i got the answer $2(44-6)$ but my books' answering scheme says it is $7600$ please help me!
3
votes
3answers
58 views

If $1$ was a prime, could it be possible for the prime factorization of any number to go on forever?

If $1$ was a prime, could it be possible for the prime factorization of any number to go on forever? I think this would happen because if you multiply anything by $1$, you get the first factor ...
1
vote
1answer
32 views

proof that $n$ is prime or has prime factor $\leq \sqrt{n}$

apparently my attempt proof is wrong says the chat person will, so can you guys tell me how to fix please :) Show that any integer $n \gt 1$ is either a prime or has as a factor a prime $\leq ...
1
vote
1answer
33 views

Is it a good idea to use a factor tree to find the prime factorization of any composite number? Why or why not?

For example, if I use a factor tree for 12, I would know a couple of ways to do it, but I'm going to show you one way: 12=3 x 4: 4 is composite, so 4=2 x 2. We can't factor down any further, so I ...
1
vote
0answers
32 views

prime case function?

Does there exist a name (or assigned to a mathemtician) for a case function $f(x)$ in literature, such that it twould take the value $1$ when $x$ primes, and zero otherwise? I am just looking for a ...
6
votes
2answers
58 views

Conjecture about the powers of 2 in the prime factorizations of the series $a_n = n(n+1)(n+2)$

I found the following law and would like to know what do you think about it and if anyone can explain why this is so. Also, is this already known and proven? Consider the following series: ...
2
votes
0answers
24 views

Largest prime factor of a Mersenne number with exactly two prime divisors

For a prime $p$, let $M_p = 2^p-1$ be a (Mersenne) number with exactly two prime divisors, and let $P(p)$ be the largest of these two. Clearly $P(p) > \sqrt{M_p}$. This is very likely a hard ...
0
votes
0answers
74 views

Logic puzzle of two numbers

The puzzle goes like this.. ...
1
vote
1answer
25 views

Prove that if $p\le n$, then $p$ does not divide $n! + 1$

I'm having trouble on how to approach this problem Prove that if $p\le n$, then $p$ does not divide $n! + 1$ ($p$ is prime and $n$ is an integer).
1
vote
1answer
31 views

Notation for power of prime in prime factorization

What's the accepted shorthand for the power of a prime in the prime factorization of a natural number? For example, $35 000 = 2^3 5^4 7$, so what would the notation be for $f_5(35 000) = 4, f_2(35 ...
0
votes
2answers
16 views

Prime Factorizations that divide each other

Let n have prime factorization n = p^s1 · p^s2 · · · p^sk and let m have prime factorization m = q^t1 · q^t2 · · · q^tl If n|m, what must be true about the corresponding lists of primes and the ...
1
vote
2answers
48 views

Factorization with smart way.

$3^{15} + 1 = 14348908$ How to factorize it without using calculator. Please me give. I can only do: $3^{15} + 1 = 14348908 = (3+1)(3^{14}-...+ 1)$
0
votes
0answers
24 views

Quadratic Sieve, matrix problem

I read this: Quadratic Sieve Matrix Reduction and I am basically stuck. My Gaussian elimination says the answer is v= 0,0,0. Although you can clearly see that the correct answer is (1,1,1). How does ...
0
votes
2answers
50 views

Division algorithm and Prime Numbers

In my class, the professor went through a proof that if $p|xy$ then $p|x$ or $p|y$. where p is a prime number. And now that I am reading through it, there is a small piece of the proof that I do not ...
2
votes
2answers
41 views

Total possible combinations of primes

I have been working on a problem as follows: Do there exist 100 consecutive natural numbers none of which is prime? I know that the answer is 'yes', by considering 101!, and noting the sequence 101! + ...
1
vote
1answer
19 views

If $f \mid h, g\mid h$ and $f,g$ are relatively prime, then $fg\mid h$?

Let $f,g,h \in\mathbb{F}[x]$, with $f$ and $g$ are relatively prime. If $f\mid h$ and $g\mid h$, prove that $fg\mid h$. What I've done so far: Experimenting with natural numbers, I suspect that ...
1
vote
0answers
28 views

Algorithm to compute prime factors of n from whether x is a square?

Suppose there exists an algorithm that takes input $x \in \mathbb{Z}_{n}^{*}$ and returns the square root of $x$ if $x$ is a perfect square and nothing otherwise. Use this algorithm to compute the ...
2
votes
0answers
75 views

Prime Factor Problem To Solve

For any positive integer $n>10$, $\lfloor \sqrt{n!}\rfloor$ has always a prime factor $> n$.
0
votes
0answers
79 views

What is the name of this proof of, “$\sqrt{2}$ is irrational”?

Usually the proof of $\sqrt2$ is irrational is done by contradiction(e.g. here), but I found another similar but short proof in the book "Beginning Algebra for College Students" by Lloyd Lincoln ...
3
votes
1answer
39 views

Euclid's lemma for non-prime numbers.

I was trying to prove that $\sqrt{6}$ irrational as: Let $$\sqrt{6}=\dfrac ab$$ $$\implies a^2=6b^2$$ $$6|a^2 \implies 6|a$$. I should not be able to do the step because 6 is not a ...
0
votes
3answers
41 views

Show $F_n$ has a least element and it is prime. [closed]

let $F_n$ be the set of positive factors of n greater than 1 and $n\in \mathbb{N}$. Show $F_n$ has a least element and it is prime.
1
vote
1answer
40 views

Prime factorization difficulty

From Wikipedia: Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime ...
0
votes
0answers
39 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
2
votes
0answers
80 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
1
vote
1answer
25 views

Prime factorization, how does it work?

When finding the prime factors of a given number, it is enough to divide n by x where x is the smallest number which n can be divided evenly by, this process is then repeated until n can no longer be ...
7
votes
1answer
82 views

Irreducibility of an integer polynomial with exponents in linear sequence?

Let $b$ and $n$ be two positive integers. Is there are a general result which tell us when the polynomial $$1+x^{b}+x^{2b}+x^{3b}+\cdots+x^{nb}$$ is irreducible over the integers? I know that ...
-2
votes
0answers
27 views

A question about prime and factorization [duplicate]

Find a prime number $p$ and an integer $b < p$ such that $p|(b^{p−1} − 1)$. Need help guys
2
votes
3answers
64 views

Number of solutions of polynomials in a field

Consider the polynomial $x^2+x=0$ over $\mathbb Z/n\mathbb Z$ a)Find an n such that the equation has at least 4 solutions b)Find an n such that the equation has at least 8 solutions My idea is to ...
0
votes
0answers
27 views

Estimate, using the Knuth-Trabb-Pardo table, how many values of $r$ would be needed in order to factor…

Use the Knuth-Trabb-Pardo table to estimate, for the original Quadratic Sieve, with all $r \ge \sqrt{n}$, approximately how many values of $r$ would be needed in order to factor a forty-digit ...
0
votes
0answers
12 views

Axiom of extensionality and Venn diagrams to derive GCD

This is mostly a question of what kind of language to use when explaining the following so as to be rigorous. The wikipedia article on GCD presents a nice intuitive Venn-diagram-based way to derive ...
3
votes
1answer
61 views

How to write $210\in\mathbb Z[\sqrt{-1}]$ as a product of prime elements?

How can I write $210\in\mathbb Z[\sqrt{-1}]$ as a product of prime elements? Progress I factored $2\in\mathbb Z[i]=(1-i)(1+i)$ and $5\in\mathbb Z[i]=(2-i)(2+i)$. I cannot do it for $3$ and $7$ ...
0
votes
1answer
45 views

Generator of $Z_p^*$ with large p

I have to find a generator for $Z_{p}^*$. The prime number p is $2425967623052370772757633156976982469681$. My prime factors for (p-1) is according to 1 ...
0
votes
0answers
4 views

Example of factorization using Montgomery curves

I have programmed the elliptic curve method for integer factorization using Montgomery curves(the same idea as Lenstra's elliptic curve method, just changed a bit so it works with Montgomey curves). ...
2
votes
1answer
57 views

Prime Factorization and Number Theory

Prime factorization of $n$ is $$n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$$ Let $f(n) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ where $e_k=a_k$ if $p_k|a_k$, else $e_k=a_k-1$ I want to ...
1
vote
0answers
32 views

Fundamental Theorem of Arithmetic (Canonical) missing crucial step

I've worked long on the proof of the fundamental theorem of Arithmetic and there is only one tiny piece left I can't wrap my head around. Suppose that $$\prod_{i=1}^r p_i^{m_i} = \prod_{j=1}^s ...
1
vote
1answer
51 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
1
vote
1answer
28 views

Simplifying square roots?

How would I simplify $\sqrt{\frac{800}{3}}$ preferably by a factor tree? I know it simplifies into $\frac{20\sqrt{6}}{3}$. I just don't know the steps to get there. Help please?
7
votes
1answer
160 views

How does (21) factor into prime ideals in the ring $\mathbb{Z}[\sqrt{-5}]$?

The text of the exercise is the following: Show that $\mathbb{Z}[\sqrt{-5}]$ is a Dedekind domain, and that the identities $21 = (4+\sqrt{−5}) \cdot (4 − \sqrt{−5})$ and $21 = 3 · 7$ represent two ...
2
votes
1answer
60 views

Generate evenly spaced points on 2D graph

I want to draw dots on an image that is W by W pixels. The image is stored as a 1-D array of pixels. The pixel (x,y) is at array index x + y * W. I am thinking that I can use a fixed step size, N, ...
2
votes
2answers
57 views

If $q$ is a prime $\leq p$, then $q$ divides $p\# − q$

If $q$ is a prime $\leq p$, then $q$ divides $p\# − q$ What does this mean? I know that it is related to something which I have been studying, but what does $p\# − q$ mean? I am only beginning to ...
0
votes
0answers
64 views

Prime Reflections

How would you describe the following pattern?: For each primorial from 30 onward, there exists a pattern in the arrangement of the prime factors of the composite numbers which I call "the mirror ...
0
votes
1answer
43 views

A function that maps a value to a large prime

I'd like to ask whether there is any function that maps a value to a large prime in deterministic way, so this function always maps the same value to the same large prime. The large prime here ...
1
vote
1answer
40 views

One Half of a Primorial

Is there a name for a half primorial? How should a half primorial be notated? The first three primorials are 2,6, and 30. The first three half primorials are 1,3, and 15. I have found that the half ...
3
votes
0answers
26 views

Given $n$, find $a,b$ such that $a+b=n$ and $\Omega(a)+\Omega(b)$ is maximized

Given a number $n$, find $a,b$ such that: $a,b$ non-negative integers $a+b=n$ $\Omega(a)+\Omega(b)$ is maximized $\Omega(n)$ counts the number of prime factors of n (with multiplicity). ...
4
votes
0answers
45 views

Numbers Made From Concatenating Prime Factorizations

I came across the following curious problem while playing around with my calculator. Take any positive integer $n$; for this example we'll use $216$. Create a sequence as follows: Factor $n$ into ...