All Questions
9
questions
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
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
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
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
1
vote
1
answer
823
views
How to find modulo using Euler theorem?
I don't know how that's possible using phi, the question starts with this one:
a) Decompose 870 in prime factors and compute, ϕ(870)
I know how to resolve this, first 870 = 2*3*5*29 and ϕ(870)= ...
- 31
0
votes
1
answer
73
views
Prime power decomposition
$x^{147} \equiv (((x^{7})^{7})^{3})\equiv x^{3}(mod7)$
How does $x^{147}$ simplify into $x^{3}(mod7)$
What Corollary is responsible for this?
Edit:
Fermat's Little Theorem is needed:
147 = 3 * 7 *...
- 289
2
votes
1
answer
71
views
Proof involving modular and primes
My Question Reads:
If $a, b$ are integers such that $a \equiv b \pmod p$ for every positive prime $p$, prove that $a = b$.
I started by stating $a, b \in \mathbb Z$.
From there I have said without ...
- 1,088
2
votes
1
answer
2k
views
attack on RSA (factoring when knowing e and d)
This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
- 23