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
votes
0answers
63 views

Factorization and primality test of Lepore-Santo in logarithm. There is something faster? [on hold]

Factorization and primality test of Lepore-Santo in 4*log [(Y-X)/6]+1 I will show you the basic example, that i sto say the factorization of two prime numbers because reterating this process we can ...
-4
votes
0answers
26 views

Factoring problems [on hold]

I have problem for factoring this 98 digit number : 33 854 167 302 714 697 655 776 456 809 005 268 861 013 370 491 967 978 835 349 122 035 029 100 536 990 622 539 607 392 138 825 453, could you help ...
-1
votes
0answers
14 views

Is the rule of factorization remain same at all condition on mathematics? [on hold]

Some one said to me from needpaperhelp.com that the rules of mathematic factorization are remain same at all condition of the mathematics ??
0
votes
0answers
23 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
73 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
53 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
37 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
40 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
14 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
212 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
38 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
12 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
27 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
31 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
74 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
25 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
32 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
57 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
23 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
50 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
64 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
20 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
67 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
114 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
23 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
32 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
31 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
81 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
66 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
48 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 ...
5
votes
2answers
185 views

prove that $f_n = 37111111…111$ is never prime

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 ...
1
vote
0answers
8 views

Factorization of sum and difference of factorized coprimes

If I have the prime factors of two coprimes $a$ and $b$, is it possible to find the prime factors of $a + b$ and $a - b$ faster than a full factorization?
0
votes
2answers
111 views

Prove that if $ n > 2 $ then between $n$ and $n!$ is at least one prime. [duplicate]

Prove that if $ n > 2 $ then between $n$ and $n!$ is at least one prime. Ok I can see that it's obviously true, but what to use to prove it?
3
votes
2answers
40 views

What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?

Same question as in title: What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ? I know how to count number of them using Euler's function, but how to calculate sum?
9
votes
4answers
1k views

Why is every prime number ($5$ and higher) divisible by $24$ (into a whole integer) when you square it and subtract $1$? [duplicate]

I asked this question on puzzling.se and someone suggested I post it here: I discovered this by accident, when trying to create a formula that generates prime numbers (an impossible task, I know). ...
-2
votes
1answer
35 views

Encoding conditions into single number

I have N boolean conditions such as: [condition_1:true], [condition_2:true], [condition_3:false], [condition_4:true]. I can present it as following: Using binary numbers, e.g., 1101 single int32. ...
0
votes
2answers
52 views

Prove that every number between two numbersis composite

I have this problem, and I have no idea how to go about it: Let $p_1,p_2, \ldots, p_{n+1}$ be the first $n+1$ primes, in order. Prove that every number in between $p_1 \cdot p_2 \cdot p_3 \ldots ...
0
votes
1answer
80 views

Factorizable huge semiprime

I'm trying to understand how the number decimal The correct decimal number is: ...
2
votes
1answer
73 views

Why does $\sum\limits_{k=1}^\infty \lfloor m/(n^k)\rfloor$ give you the number of times that $n$ divides $m!$? [duplicate]

If $n$ is a prime less than $m$, with $n,m \in \mathbb N$, why does $$\sum_{k=1}^\infty \left\lfloor \frac{m}{n^k}\right\rfloor$$ give you the number of times that $n$ divides $m!$? Examples: $n=13$ ...
0
votes
1answer
40 views

Sieve improvement for Fermat's factorization method

I been reading the wiki article about, Sieve improvement for Fermat's factorization method. And I don't understand the mode 16 example, I understand why $a^2$ must be $9$. But why $a$ must be $3$ or ...
3
votes
2answers
113 views

The ultimate formula to factor them all.

Context I am working on Integer factorization problem, I found a formula for factoring numbers, and I need your help to simplify it. First I will explain how I get there and then I present the ...
3
votes
2answers
71 views

When $\sqrt{(x+a)^2 -b}$ is an integer?

While working on integer factorization problem, I came to this: How to find for which values of $x$ the next equation is an integer? $$\sqrt{(x+a)^2 -b}$$ $a,b$ are positive known integers In ...