All Questions
Tagged with prime-factorization modular-arithmetic
93
questions
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
3
votes
1
answer
58
views
Divisibility of numbers in intervals of the form $[kn,(k+1)n]$ [duplicate]
I have checked that the following conjecture seems to be true:
There exists no interval of the form $[kn, (k+1)n]$ where each of the integers of the interval is divisible by at least one of the ...
- 1,190
0
votes
0
answers
42
views
About the proof of reduction of factoring to order finding
Inside the book I'm following there's a theorem, used to prove the factoring algorithm, which states:
Suppose $N = p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{m}^{\alpha_m}$ is the prime factorization of ...
-1
votes
1
answer
46
views
Finding common modulo
given these two modulo equations $c_1 = m_1^a (\mod n)$, $c_2 = m_2^a (\mod n)$
Where '$a$' is prime and $n$ is a product of two primes, and the only unknown is $n$, is it possible to solve for $n$? I ...
- 9
2
votes
1
answer
68
views
How to solve $x^x \equiv 0 \pmod y$
Given a constant y, I am trying to find the smallest value for x that satisfies the equation $x^x = 0 \mod y$. So far I have been able to determine that $x$ is equal to the product of all the prime ...
- 21
3
votes
1
answer
147
views
Is the number of ways to express a number as sum of two coprime squares same as number of solution of $x^2+1\equiv0\pmod n$
The number of representations of $n$ by sum of 2 squares is known as sum of square function $r_2 (n)$. It is known that if prime factorization of $n$ is given as
$$2^{a_0}p_1^{a_1}p_2^{a_2}\cdots q_1^{...
- 3,589
4
votes
0
answers
243
views
Proper divisors of $P(x)$ congruent to 1 modulo $x$
Let $P(x) $ be a polynomial of degree $n\ge 4$ with integer coefficients and constant term equal to $1$. I am interested in Polynomials $P(x) $ such that for a fixed positive integer $b$, there are ...
- 234
1
vote
1
answer
50
views
Probability a random number $M$ is not a factor of $N$
Let $N$ be some positive integer and let $S := \lbrace 1, 2, \cdots, \log^2(N) \rbrace$ (pretending at $\log^2(N)$ is an integer). Suppose $M$ is randomly chosen from the set $S$. The goal is to use ...
- 549
1
vote
0
answers
84
views
Find the remainder when the $2006! + \dfrac{4012!}{2006!}$ is divided by $4013$
$$2006!+\frac{4012!}{2006!}=x \pmod{4013}$$
Answer: $x=1553.$
Solution: $$2006!+4012!/2006!=x\pmod{4013}$$
$$(2006!)^2 -2006!x+4012!=0\pmod{4013} (*)$$
$$4\cdot (2006!)^2-4\cdot 2006!x+4\cdot 4012!=...
- 11
0
votes
0
answers
55
views
Why is this not sufficient proof of the divisibility of $\binom{p}{j}$ by $p$.
In my text book there's an example of a proof on why $\binom{p}{j}$ is divisible by $p$, with $p$ prime, for $0<j<p$. Firstly, it shows that
$$\binom{p}{j}=p\frac{(p-1)!}{j!(p-j)!}$$
From this ...
- 3,468
-1
votes
1
answer
161
views
Computing (quickly) the multiplicity of a (prime) divisor
Question
I have a fixed, prime d and an n < 2⁶⁴, and I want not only to compute whether d ...
- 99
1
vote
2
answers
162
views
Finding all no-congruent primitive roots $\pmod{29}$
Finding all no-congruent primitive roots $\pmod{29}$.
I have found that $2$ is a primitve root $\pmod{29}$
Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$
Then I ...
- 113
0
votes
1
answer
44
views
Does there always exist a prime $q\equiv3\mod 4$ that divides $p+a^2$ with $p\equiv1$ mod 4
Let $p$ be a prime such that $p\equiv1\mod4$. Is it true that there will always exist a prime $q$ that satisfies $q\vert(p+a^2)$ and $q\equiv3\mod4$, for some integer $a$?
I have tried proceeding by ...
- 103
0
votes
1
answer
351
views
Find integral solution using congruence modulo.
Find integral solution to $a^3 - 1100 =b^3$ using modular arithmetic.
No integral solutions for this exist, so how to prove using modular arithmetic?
Earlier I had asked about $a$ and $b$ being ...
- 11
1
vote
1
answer
128
views
For $n \ge 4$ find a factorization $n^2 - 3n + 1 = ab$ where $a \lt n$ and $b \lt n$.
Update: We can use Willie Wong's argument to justify the definition of a 'truth cutoff' function,
$\quad \psi: \{3,4,5,6, \dots \} \to \{4,5,6,7, \dots \}$
For convenience we start with a ...
- 11.5k
1
vote
2
answers
221
views
Find the least odd prime factor of $155^8+1$
Find the least odd prime factor of $155^8+1$. How do I do this without using Wolfram Alpha or something?
- 783
1
vote
0
answers
122
views
Sum of members from multiplicative group of prime order $k$ modulo prime $P$? $c$ in: $\sum_{n=1}^{k} (g^n \bmod P) = c \cdot P$ ($g$ prime order $k$)
Let $P$ be a prime ($>2$) and $g$ a value between $2$ and $P-2$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a ...
- 77
2
votes
1
answer
106
views
Integer Factor Congruence
Given an integer $N$, with unknown prime factors $f_1$, $f_2$ ... $f_n$, and given unique integers $k_1$, $k_2$ ... $k_n$, with $\sqrt{N} \geq k_i>2$ for all $i$ such that
$$f_1 \equiv 1\pmod {k_1}$...
- 365
9
votes
3
answers
371
views
Can $7$ be the smallest prime factor of a repunit?
Repunits are numbers whose digits are all $1$. In general, finding the full prime factorization of a repunit is nontrivial.
Sequence A067063 in the OEIS gives the smallest prime factor of repunits. ...
- 221
3
votes
1
answer
126
views
The proof of $(n+1)!(n+2)!$ divides $(2n+2)!$ for any positive integer $n$
Does $(n+1)!(n+2)!$ divide $(2n+2)!$ for any positive integer $n$?
I tried to prove this when I was trying to prove the fact that ${P_n}^4$ divides $P_{2n}$ where $n$ is a positive integer, where $P_{...
- 438
0
votes
1
answer
196
views
Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Question: Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Apparently, the answer is all prime numbers except $2, 3, 7,$ and $19.$ I did some prime factorisation and found ...
- 315
1
vote
1
answer
80
views
Given 2 functions $f(x)$ and $g(x)$ find a value where $g(x)$ divides $f(x)$ meaning $f(x) = 0 \mod g(x)$
Problem:
Given 2 functions $f(x) = 2^{p-1} + x*p$ and $g(x) = 2 * x * p + 1$ find the values where $f(x) = 0 \mod{g(x)}$, where $p$ is a prime number and $x$ is a non negative integer in the range $1,...
- 13
0
votes
1
answer
154
views
How to find the prime factors when knowing some congruence?
In order to factorize the integer $N = 67591$, choose a factor base $\{2,3,5\}$ and four congruences: $24256^2 \equiv 2^9 \cdot 3^4(mod\ N)$; $59791^2 \equiv 2^2 \cdot 3^4\cdot 5^2(mod\ N)$; $23541^2 \...
- 33
0
votes
2
answers
114
views
Proving the divisibility of $4[(n-1)!+1]+n$ by $n(n+2)$ in the condition of $n,n+2 \in P$ where $P$ is the set of prime numbers [duplicate]
Let $n$ and ($n+2$) be two prime numbers. If any real value of $n$ satisfies that condition, then prove that $$\frac{4{[(n-1)!+1]}+n}{n(n+2)} = k$$ where $k$ is a positive integer.
SOURCE: BANGLADESH ...
- 1,188
1
vote
2
answers
79
views
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $x\in\mathbb{N}$, is $5$ or $1$ mod $5$
We can write the "polynomial" as follows:
$$x^4+x^3+x^2+x+1=\frac{x^5-1}{x-1}.$$
For even $x=2y$, we have that $x^5-1=(2y)^5-1=32y^5-1\equiv1$ mod $5$.
For odd $x=2y+1$, we have that $(2y+1)^5-1\...
- 1,674
1
vote
0
answers
43
views
Non-Linear Diophantine Equation in Two Variables [duplicate]
How many solutions are there in $\mathbb{N}\times \mathbb{N}$ to the equation $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{1995}$ ? I could solve till I got to the point where $1995^2$ is equal to the ...
- 344
1
vote
1
answer
89
views
Find X in the Equation
I'm not a mathematician and I have forgotten about some basics in mathematics.
I have this equation:
$$x^y \pmod z = w$$
Given $y, z,$ and $w,$ how will I find $x$? How will I get the equation for $...
- 223
0
votes
0
answers
79
views
Finding the smallest prime factor of $\sum_{a=1}^N a^{k}$
This question is linked to my previous question, but I wanted a clearer explanation.
Suppose we have a huge number of that type with a huge $k$.
$$\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k},$$
...
- 349
0
votes
1
answer
165
views
Find the smallest positive prime divisor of ...
Problem:
That's a problem I have found on the web. I didn't understand the solution:
Why??
Given solution:
How all this sequence has been transformed into $$33-{\lfloor {33\over p}\...
- 349
7
votes
2
answers
2k
views
What is the multiplicative order of a product of two integers $\mod n$?
Standard texts prove that $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ when $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. What if they are not relatively prime? Here $\textrm{...
- 11.8k
1
vote
0
answers
39
views
Baby steps to factorization of a large composite number via modular arithmetic
Given a huge composite number with unknown prime factors and a much smaller prime modulus P, is there a way (short of the Herculean task of factorization) to identify the residue classes mod(P) of the ...
- 111
3
votes
1
answer
113
views
What does it mean for $\sigma^N$≡$\sigma^e$ (mod N) for arbitrary a?
Full disclosure: I am trying to solve a homework problem.
As part of a homework problem, we were given a large semiprime $N$, which was used as both the modulus and the public key and asked to ...
- 259
5
votes
1
answer
224
views
An approximation for $1\leq n\leq N$ of the number of solutions of $2^{\pi(n)}\equiv 1\text{ mod }n$, where $\pi(x)$ is the prime-counting function
We denote the prime-counting function with $\pi(x)$ and we consider integer solutions $n\geq 1$ of the congruence $$2^{\pi(n)}\equiv 1\text{ mod }n.\tag{1}$$
Then the sequence of solutions starts as $$...
user243301
0
votes
2
answers
71
views
Find all $x \in \mathbb Z_{360}$ such that $x^2 ≡ 0 \pmod{360}$
Find all $x \in \mathbb Z_{360}$ such that $$x^2 ≡ 0 \pmod{360}.$$
I know that this means to find all $x$ such that the result divides into $360$ evenly. I also know the prime factorization of $$360 =...
- 689
2
votes
1
answer
142
views
The Chinese hypothesis revisited
In the past I tried to get different variations of the so-called Chinese hypothesis, see this Wikipedia (a disproven conjecture).
Today I wanted to combine in an artificious way also Wilson-Lagrange ...
user243301
2
votes
0
answers
505
views
Using factorization to solve modulo arithmetic involving big numbers.
In one of my classes, the following approach was shown to solve modulo operations involving huge numbers:
Problem to solve:
49 10 mod 187.
Approach taken:
Prime factorize $187$. It's factors are ...
- 141
0
votes
1
answer
80
views
Can at most $3$ distinct primes divide $n^3-n$, for infinitely many $n$?
My assignment asks me to prove that there are only finitely many $ n\in\mathbb{N} $ such that the prime factorization of $n^3-n$ is of the form $p_1^{r_1} p_2^{r_2} p_3^{r_3}$ for $p_i$ primes and $...
- 31
3
votes
0
answers
114
views
If 13 does not divide m, then prove that $m^4+8$ is not a cube of an integer [closed]
My question is how can we prove that $m^4 + 8$ not a cube of an integer if
$m$ can not be divided by 13.
What I have done so far:
By Fermat’s Little Theorem:
\begin{align}
m^{p-1} &\equiv 1 \...
- 111
2
votes
1
answer
115
views
Prime factors of $5 n^4 - 70 n^3 + 380 n^2 - 945 n + 911 $
Let $n$ be an integer.
Then any prime factor of
$$ 5 n^4 - 70 n^3 + 380 n^2 - 945 n + 911 $$
Must be congruent to 1 mod 10.
Also
Let $n$ be an integer.
Then any prime factor of
$$ 5 n^4 - 10 n^3 +...
- 16.4k
-1
votes
1
answer
125
views
Found $a^2\equiv b^2(\mod RSA\_1024)$ What are the chances?
Due to the size of the numbers, I am writing them as a code. Below are $a$ and $b$
...
- 1,450
7
votes
0
answers
174
views
I found a way to calculate Quadratic min mod $N$, but why does it work?
I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:
$$a^2\equiv b(\mod{N})$$
If I am able to find $b$ that is a perfect square, I will be able to factor $N$...
- 1,450
0
votes
1
answer
124
views
Find integer $x$ such that $x^2 \mod {1799832043}$ is divisible by $67610791$
Find integer $x$ such that $x^2 \mod {n}$ is divisible by $p$
For values $n = 1799832043, p = 67610791$
I have been using Tonelli-Shanks algorithm to solve this and it works for small primes with ...
- 1,450
0
votes
1
answer
28
views
How hard is it to find $k = j(ed-1)$ in RSA signature
In RSA signatures the below formulas come into play:
$N=rq$ where $r$ and $q$ are large primes
$ed=1 \mod{\varphi(N)}$ where $e$ is small number with no common division with $\varphi(N)$
$a=m^d \...
- 1,450
0
votes
2
answers
86
views
Why $\gcd(a,a+N) =1$
By experiment, I notice that $$\gcd(a,a+N) =1$$
Where $N$ is a big composite integer number that is hard to factor and does not have a common divisor with $a$. And $a$ is a positive big integer that ...
- 1,450
0
votes
0
answers
42
views
How to simplify $2^{a\left(2^{bc}-1\right)}-1\mod{N}$
How to simplify $$2^{a\left(2^{bc}-1\right)}-1\mod{N}$$
Where a,b,c are big integers with relatively small primes and N is a big integer that is hard to factor(it does not have small primes).
I have ...
- 1,450
1
vote
0
answers
299
views
Pohlig-Hellman algorithm
I'm trying to use the Pohlig-Hellman algorithm to solve for $x$ where $15^x=131(\bmod 337)$. This is what I have so far:
prime factors of p-1: $336=2^4*3*7$
$q=2: x=2^0*x_0+2^1*x_1+2^2*x_2+2^3*x_3$
...
- 297
1
vote
6
answers
2k
views
Sum of positive divisors if and only if perfect square
let n be a positive odd integer, prove that the sum of the positive divisors of n is odd if and only if n is a perfect square.
I know that based on the prime factorization theory that every integer n ...
- 689
1
vote
0
answers
198
views
Proving a number is a factor of a in (a mod N)
Suppose you had a very large composite number, which is the product of a couple large primes. Let's call this $a = c_1c_2c_3c_4$ where $c_1,c_2,c_3$ and $c_4$ are all primes.
If you calculated $d = ...
- 111
0
votes
0
answers
67
views
Is $(2^a - 3^b)$ mutually prime with $(2^a - ((2^a)^{-1} \mod 3^b ) - ((3^b)^{-1} \mod 2^a))$?
Is $(2^a - 3^b)$ mutually prime with $(2^a - {{[2^a]}^{-1}}\mod 3^b + [3^b]^{-1}\mod 2^a)$, provided that $a\geq b$ and $b>0$?
By $[2^a]^{-1}\mod 3^b$ I mean "the multiplicative inverse of $2^a\...
- 440