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

Consecutive numbers with less than $k$ prime factors?

Let $k$ be an integer. Consider the consecutive numbers with less than $k$ distinct prime factors. Are there arbitary large differences between those numbers ? With other words : Are there ...
2
votes
1answer
32 views

About the ways prove that a ring is a UFD.

I'm doing an exercise where I have a commutative ring with unity $R$. We had to find that the nonunits formed an ideal (maximal). After that, we found the irreducible elements, and then we saw that ...
0
votes
1answer
20 views

Counting the spokes

I’ve been playing around with wheel factorization (Wikipedia link) and wanted to know how many spokes there are in a given wheel. For a 2-7 wheel the circumference of this would be 210 and then I can ...
4
votes
2answers
56 views

Conjecture: only one even Fibonacci term divided by two gives a prime: $F(9) = 34 = 2 \times 17$

Every Fibonacci term $F(3n)$ is divisible by two $F(3) = 2$ $F(6) = 8$ $F(9) = 34$ $...$ After seeking Fibonacci tables factorization until $F(10000)$, for every term $\frac{F(3n)}{2}$, it ...
0
votes
2answers
34 views

Where does the proof of unique factorization fail for $\mathbb Z[\sqrt{-5}]$?

I know that unique factorization does not hold for all rings, such has the much-used example $\mathbb Z[\sqrt{-5}]$. It seems that Euclid's lemma does not hold for these rings, and so on. However, ...
1
vote
0answers
16 views

Trouble finding the norm of the two following ideals

Given that $\alpha$ is the root of the polynomial, $x^3 - x - 1$ is $\alpha$ and $K=\mathbb{Q}(\alpha)$, show that the norm of the ideal $\langle 5, \alpha-2\rangle$ is $5$ and the norm of the ideal ...
1
vote
1answer
63 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
4
votes
2answers
104 views

How many ways are there to express a number as the product of groups of three of its factors?

Specifically, I am thinking of a cuboid with a given volume ($28\,000$) that has sides of integer length. For example, $20 \cdot 20 \cdot 70 = 28\,000$, but so do $10 \cdot 40 \cdot 70$ and $1 \cdot 1 ...
1
vote
1answer
52 views

relation between set of prime divisors of two positive integers

How to tell in most efficient way that the set of prime divisors of a positive integer M is a superset of the set of prime divisors of another positive integer N where M and N are quite big numbers. ...
2
votes
1answer
51 views

How to Find the smallest integer with exactly N odd divisors.

Hi All I was trying one problem in which is it asking for the smallest number having N odd divisors. As I know the smallest number having n divisors can be find easily.First we need to find the prime ...
1
vote
1answer
50 views

Upper bound on the maximal number of prime factors

I would like to prove $$\omega(n) \le \frac{\ln{n}}{\ln\ln{n}}$$ This is a quite standard result, but I haven't been able to find a proof. Here's what I've tried doing: ...
3
votes
0answers
43 views

prime divisor propertyfor Hurwitz integers

The Hurwitz integers $\mathcal{H}_{\mathbb{Z}}$ is a particular subset of quaternions. Define: $$ \mathcal{H}_{\mathbb{Z}} = \left\{ a\frac{1+i+j+k}{2}+bi+cj+dk \ | \ a,b,c,d \in \mathbb{Z} \right\} = ...
1
vote
0answers
34 views

Non-unique factorization in $\mathbb{Z}[\sqrt{-5}]$

I want to show that the decomposition into irreducible factors in the ring $$\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5}|\space a, b \in \mathbb{Z}\}$$ is not unique, except for the order of factors ...
2
votes
0answers
73 views

Can I use integer frequencies in quadratic intervals to set a lower bound for primes? [closed]

I want to find out if the following arithmetic approach could produce a backdoor proof of Legendre’s Conjecture. There are two assumptions, Questions A and B, which are posed in the text and labeled ...
0
votes
0answers
25 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
6
votes
2answers
87 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
3
votes
3answers
76 views

A doubt concerning the fundamental theorem of arithmetic

Will a prime $p^{0}$ be considered a unique prime in prime decomposition of a number? If the answer to the above question is yes then it breaks the uniqueness which the Fundamental Theorem of ...
0
votes
1answer
54 views

$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$ $\Longrightarrow $ is wrong,Tonyk note ...
0
votes
0answers
16 views

Tree structure by using integer markers

I'm trying to model a situation in witch a group of entities are organized hierarchically. We say that entity A has privileges over entity B if there a direct hierarchical connection between A and B ...
1
vote
3answers
43 views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

I was trying to prove that $$ dm = |ab|$$ where $d$ = gcd(a,b) and m = lcm(a,b). So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. ...
1
vote
0answers
44 views

Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number?

Given some $n \in \mathbb{N}$, is there a name or notation for any/all of the following? The set of all factors $F(n)$ of $n$ (including 1 and $n$). The ascending sequence of non-unique prime ...
0
votes
2answers
26 views

Asymptotic upper bound on number of solutions to $ab \equiv n \pmod m$

Does anyone know a rough upper bound on the number of solutions to $ab \equiv n \pmod m$ when $n$ and $m$ are given and $a<m$, $b<m$, $n<m$? Specifically, I want to know how the number of ...
0
votes
0answers
19 views

Help with Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound $B$ and some number $N$ and search for numbers between ...
10
votes
5answers
218 views

Which of these two factorizations of $5$ in $\mathcal{O}_{\mathbb{Q}(\sqrt{29})}$ is more valid?

$$5 = (-1) \left( \frac{3 - \sqrt{29}}{2} \right) \left( \frac{3 + \sqrt{29}}{2} \right)$$ or $$5 = \left( \frac{7 - \sqrt{29}}{2} \right) \left( \frac{7 + \sqrt{29}}{2} \right)?$$ ...
1
vote
1answer
40 views

If $a^2+3b^2$ is a cube in $\mathbb Z$ , then are $a+\sqrt{-3}b$ and $a-\sqrt{-3}b$ both cubes in $\mathbb Z[\sqrt{-3}]$ ?

If $a,b \in \mathbb Z$ are such that g.c.d.$(a,b)=1$ and if $a^2+3b^2$ is a cube in $\mathbb Z$ , then are $a+\sqrt{-3}b$ and $a-\sqrt{-3}b$ both cubes in $\mathbb Z[\sqrt{-3}]$ ? I cannot use ...
1
vote
0answers
13 views

Can you give an example of an irreducible element of the ring of Dirichlet series with integer coefficients?

According to this. The ring of Dirichlet series with integer coefficients is a UFD. Can you give an example of an irreducible element in that ring?
3
votes
0answers
28 views

Squares of finite fields (mod p*q)

Lets say we have $\mathbb{Z}_p$, where p is prime. For each element(x) we have two squares(y) so that $y^2=x$ ie if $p=7$ for $x=4$ we have $y_1=2,y_2=7-2=5,y=\pm2 $ ok, lets have ...
2
votes
0answers
35 views

The smallest prime factor with a set of digits

I was wondering if there was a way to logically/mathematically derive what the smallest possible largest prime factor to a number was, using each of the digits 1-9 only once. An example could be ...
0
votes
1answer
35 views

Interesting pattern arises when plotting prime numbers on a Cartesian plane

While plotting prime numbers out of boredom one day, I stumbled upon an interesting pattern which may be expressed as such: Let $\mathbb{N}$ be the set of natural numbers. Let $\mathbb{P}$ be the set ...
4
votes
1answer
78 views

Sum and Product Puzzle and Prime Factors

Suppose we have two number $X$ and $Y,$ such that $1 < X < Y < 100,$ and $X + Y ≤ 100.$ Sue is given $S = X + Y$ and Pete is given $P = XY.$ They then have the following conversation: ...
0
votes
0answers
31 views

Is there a pattern for the distribution of prime factor count for numbers under n?

In the below picture I have charted the distribution of numbers below n by factor count. The bottom line is for all numbers under 100,000 then 200,000 ... all the way to 1,000,000. They seem to tend ...
0
votes
0answers
35 views

Of what use is my code for finding prime numbers of a certain size?

I've developed a bit of mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
11
votes
2answers
1k views

Prime Numbers: 6k-1 mod rule (New Discovery?)

I've noticed that although all primes follow the pattern of $6k - 1$ and $6k + 1$ which seems to be a somewhat known fact. However, I also noticed that all the primes of the pattern of $6k - 1$ only ...
1
vote
0answers
34 views

When looking at the mod as binary value

Look at the next value: $$617*947 = 584299$$ 617, 947 are prime values. I want to see what are all the possible solutions for the next equation, for $k=4$: $$(a\mod k)(b\mod k) = 584299\mod k$$ ...
2
votes
1answer
61 views

Factorization of a prime ideal in a integral extension.

If $R\subseteq R'$ are integral extensions of Dedekind rings, and $0\neq\mathfrak p$ is a prime ideal of $R$ then $R'\mathfrak p\neq R'$. Do you know an example $R'\mathfrak p=R'$?. Of course ...
0
votes
1answer
24 views

Analogue to superior highly composite numbers for the unitary divisor function

For which positive integers $n$ does there exist a positive real number $\epsilon$ such that $\dfrac{2^{\omega(n)}}{n^\epsilon}\geq\dfrac{2^{\omega(k)}}{k^\epsilon}$ for all $k<n$, and ...
1
vote
1answer
54 views

Integer factorization with sieving

I am trying to solve the Integer Factorization problem using the sieving method, and I was wonder if there been a study in this area and if there more on this topic that I can read? Note, I am not ...
0
votes
2answers
65 views

Find the number of trailing zeroes. [duplicate]

Find the number of trailing zeroes. $k=1^1\times 2^2\times 3^3\times \cdots \times100^{100}$ It usually involves calculating number of $5$'s in $5^5\times 10^{10}\times 15^{15}\times \cdots\times ...
0
votes
1answer
22 views

Is there a probabilistic prime test with time complexity log^p (p<1)?

My question is: Is there a (possibly probabilistic) prime test with sub-logarithmic runtime complexity? Is it possible to construct one? I have found the following complexities for the most common ...
2
votes
1answer
68 views

Proof for a statement on prime numbers

I read the following statement: We can define the number $$x=2^0\cdot 3^1\cdot 5^2\cdot 7^3\cdot\ldots\cdot b^n$$ where $b$ is the $n$'th prime number. That is, $b$ is the $n$'th prime number if ...
1
vote
0answers
26 views

Prove that if k and j are relatively prime to n, then so is k * j modulo n

GCD(kj, n) = 1 as kj and n don't share common prime factors. kj=qn + r for some q let's construct linear combinations ks + nt = 1 ju + nv = 1 Multiplying left-hand and right-hand sides (kj) su + ...
4
votes
3answers
119 views

When is the number of $N$'s factors $1 + \sqrt{N}$?

(Answer: Only $N = 4$ and $N = 16$.) The following question arose in a course for pre-service and in-service elementary school teachers: For what $N \in \mathbb{N}$ is it the case that the ...
2
votes
2answers
22 views

proof : $a,b \in N, a^5 | b^5 \rightarrow a | b$

I couldn't find anything to use apart from the fundamental theorem of arithmetic. Here is my proof : Let $a,b \in N$ Suppose $a^5 | b^5$ Let $S = \{ \text{ n is prime } , n | a \lor n | b \} $ $ ...
0
votes
1answer
25 views

Exact power of prime that divides an (unrelated) number

I am trying to understand a paper where a numerical algorithm is described. I do not understand the point where the expression "exact power of a prime that divides a number" is used. Here is the ...
0
votes
0answers
35 views

Theorem on the length of factor chains

Given any prime number $p_i$, define the base factor chain $B(p_i)$ as the sequence of numbers $2,3,4,5,6,...,p_i-1$ reduced into their lowest prime factors. i.e $B(17) = ...
0
votes
0answers
34 views

Symmetric mod game

$N$ is a big integer value, with only two non trivial factors. Value $k$ will be Symmetric mod if and only if, all the possible nontrivial factors of $N$ will be ...
0
votes
1answer
106 views

Show that every prime factor of $4t^2 + 1$ is equivalent to 1 modulo 4

Show every prime factor of $4t^2 + 1$ is equivalent to 1 modulo 4 My working so far: I want to use the first Nebensatz, so given q is a prime factor I want to show $(-1/q)=(-1)^{(q-1)/2}=1$ as this ...
3
votes
0answers
68 views

Do there exist any cycles for these number sequences?

We define, for $k\in\mathbb{N}$, the sequence $\left(S_{k,n}\right)_{n\in\mathbb{N}}$: $$S_{k,1}=k,\;\;\; S_{k,n+1}=p_1q_1\cdots p_mq_m \text{ (written out in decimal)}$$ Where $p_1^{q_1}*\cdots ...
2
votes
0answers
52 views

Multiplication Sieving

Background I made another improvement to Fermat's sieve factorization, by merging the sieves groups of $4,3,5,7,11,13,17$ in two one big group. This method allows me to reduce the values that I need ...
6
votes
2answers
199 views

prove that $f_n = 37111111…111$ is never prime [duplicate]

Let $$f_n = 37111111...111$$ with n 1's. Prove that $$f_n$$ will never be prime for $$n\ge1.$$ I tried to look $$f_n$$ in mod(p), assuming $$f_n$$ is prime, for the sake of contradiction. I also ...