I know that I need to reduce $7^{12341} \pmod {1000}$ By Euler I have $7^{\phi(1000)}\equiv 7^{400}\equiv1\pmod{1000}$ That leaves me with the monster $7^{341}\pmod{1000}$ Is there a way to reduce this smoothly without working $7^2, 7^4, 7^8$ etc manually ?

I’m working on some Chinese Remainder problems and it doesn’t seem like I have the procedure down correctly. I’ll list the steps I’m taking so hopefully someone can spot what it is I’m doing wrong. Find the least nonnegative solution of each system of congruences below. $x \equiv 3 \space mod \space 4$ $x \equiv […]

I made a proof by contradiction. Suppose $δ=(a+b,\operatorname{lcm}[a,b])$ and let it be that $δ\neq(a,b)$. Then $\exists ε\big(ε=(a,b) \land ε\gt δ \big) \implies ε|a \land ε|b \implies ε|(a+b)$. It is also true that $ε|\operatorname{lcm}[a,b]$. By the two previous statements, we get that $ε|(a+b,\operatorname{lcm}[a,b])\implies ε|δ$. This is absurd since $ε>δ$. Thus $δ=(a,b)$. Is it correct? I wonder […]

This problem is taken from Ivan Niven’s “An Introduction to the Theory Of Numbers”. Show that ${{p^\alpha-1}\choose{k}} \equiv ({-1})^k\pmod p$. Note: This is not similar to this one, as $k! | p^\alpha$ is possible. My Attempt: We proceed by induction on k: Let, ${{p^\alpha-1}\choose{k-1}}=r$.Let $k=p^t*q \ : t<\alpha$. $(k,p^\alpha-k)=p^t$. $${{p^\alpha-1}\choose{k}} = {{p^\alpha-1}\choose{k-1}}*\frac{p^\alpha-k}{k}={{p^\alpha-1}\choose{k-1}}*\frac{p^{\alpha-t}-q}{q}$$. So, by induction […]

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have $p\nmid\binom{ap}{bp}$ and $p\nmid \binom{a}{b}$. $$\binom{ap}{bp}-\binom{a}{b}=\frac{(ap)!b!(a-b)!-a!(bp)!(ap-bp)!}{(bp)!(ap-bp)!b!(a-b)!}$$

Let $c$ be a $3^n$ digit number whose digits are all equal. Show that $3^n$ divides $c$. I have no idea how to solve these types of problems. Can anybody help me please?

If a number can be expressed as a product of n unique primes, in how many ways can the number be expressed as a difference of two squares?

Given e and d as the encryption and decryption component respectively, textbook RSA has the property $ed\equiv 1\pmod {\phi(n)} $. The requirement is that suppose there is another function $\lambda(n)$ such that $$\lambda(n) = {\phi(n)\over gcd (p-1, q-1)}$$ and $$ed\equiv 1\pmod{\lambda(n)}$$I need to prove that e and d still work as encryption and decryption components. […]

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$ I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$ But some how I feel the question wants me prove the result using indices properties (w/o factoring.. ) So I am posting it here to see if there are […]

What is the smallest positive integer $b$ so that 2014 divides $5991b + 289$? I just need hints–I am thinking modular arithmetic? This question was supposed to be solvable in 10 minutes…

Intereting Posts

Let $E$ be measurable and define $f:E\rightarrow\mathbb{R}$ such that $\{x\in E : f(x)>c\}$ is measurable for all $c\in\mathbb{Q}$, is $f$ measurable?
Real numbers equipped with the metric $ d (x,y) = | \arctan(x) – \arctan(y)| $ is an incomplete metric space
Fiboncacci theorem: Proof by induction that $F_{n} \cdot F_{n+1} – F_{n-2}\cdot F_{n-1}=F_{2n-1}$
Why is quaternion algebra 4d and not 3d?
Graph theory problem (edge-disjoint matchings)
Finding a closed subalgebra generated by functions.
Structure constants for and the adjoint representation and meaning in $sl(2,F)$
Computing Invariant Subspaces of Matrix Groups
Measurability of supremum over measurable set
Computing $x^{2017}+\frac1{x^{2017}}$ given the value of $x+\frac1x$.
Proof of the Banach–Alaoglu theorem
Is there any abstract theory of electrical networks?
Is $\int_0^\infty\frac{|\cos(x)|}{x+1} dx$ divergent?
Value of $ \sum \limits_{k=1}^{81} \frac{1}{\sqrt{k} + \sqrt{k+1}} = \frac{1}{\sqrt{1} + \sqrt{2}} + \cdots + \frac{1}{\sqrt{80} + \sqrt{81}} $?
Show that a function almost everywhere continuous is measurable