All Questions
Tagged with prime-factorization modular-arithmetic
94
questions
1
vote
1
answer
99
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,180
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,180
1
vote
0
answers
95
views
The chunking aspect of repunit prime factors [closed]
While others have already mentioned the divisibility of decimal repunits,
$$m := \frac{{10}^n - 1}{9}.$$
...
0
votes
0
answers
41
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,599
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 ...
- 244
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,408
-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
161
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