Articles of elementary number theory

Number of decimal places to be considered in division

This must be a basic question. But i need some help. What is the number of decimal places that needs to be considered normally in division operations in order to represent the dividend value as a multiple of divisor and quotient by rounding off. Example: Say i want to divide 3475934 and 3475935 by 65536. […]

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can’t be reduced. Attempt: It can’t be reduced when $\gcd(12n-6,10n-3)=1$ Here $(a,b)$ denotes $\gcd(a,b)$ $$(12n-6,10n-3)=(12n-6,2n-3)=(12n-6,12n-18)=(12n-6,12)$$ $\Longrightarrow$ It can’t be redused when $12\nmid 12n-6$ i.e when $12n\not\equiv 6\pmod{12}$ Theorem: for $ax\equiv b \pmod n$ there is a solution iff $d\mid b$ where $d=\gcd(a,n)$. In this case $\gcd(12,12)=12$ so […]

Bijection between natural numbers $\mathbb{N}$ and natural plane $\mathbb{N} \times \mathbb{N}$

This question already has an answer here: bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ [duplicate] 3 answers

Numbers of the form $\frac{xyz}{x+y+z}$

It is easy to show that every natural number $n$ can be written as $n = \frac{xy}{x+y}$ with $x,y\in \mathbb{N}$ by setting $x = y = 2n$. Now I experimented a little bit with numbers of the form $n=\frac{xyz}{x+y+z}$ and it seems that every natural number $n$ can be written this way with $x,y,z \in […]

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?