Articles of elementary number theory

Last 3 digits of $7^{12341}$

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 ?

Chinese Remainder Theorem Problem

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 […]

Let $a,b\in \mathbb{N^*}$. Prove that $\gcd(a+b,\operatorname{lcm})=\gcd(a,b)$. Is my proof correct?

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 […]

Alternative Proof of ${{p^\alpha-1}\choose{k}} \equiv ({-1})^k (mod \ p)$

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.

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)!}$$

Showing that a $3^n$ digit number whose digits are all equal is divisible by $3^n$

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…

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?

Using Carmichael function in RSA.

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}$

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 […]

Find the least number b for divisibility

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…