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 ...
- 275k
10
votes
1
answer
1k
views
When is $(p-2)!-1$ power of $p$ if $p$ is prime?
If $p$ is prime, for what values of $p$ is $(p-2)!-1$ a power of $p$? I know how to solve that when $p<5$ then $(p-1)!+1$ can be written as power of $p$.
- 21
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 ...
- 2,638
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\...
- 41.4k
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 ...
16
votes
6
answers
16k
views
prime divisor of $3n+2$ proof
I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof
I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+...
- 3
2
votes
2
answers
1k
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 ...
- 6,077
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
vote
0
answers
175
views
Check whether a no has exactly two Prime Factors [duplicate]
Is there a way to check whether an integer has exactly two prime factors(can be same) that is , it can be expressed as a product of two prime nos ?
EDIT: I dont want to find the factors i just want a ...
- 10.3k
-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 ...
- 275k
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 ...
- 5,281
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^{...
- 1,403
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
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 ...
- 275k