Articles of modular arithmetic

modulo of series summation

I have trouble with computing modulo. First, I have a summation of series like this: $$1+3^2+3^4+\cdots+3^n$$ And this is the formula which can be used to compute the series: $$S=\frac{1-3^{n+2}}{1-3^2}=\frac{3^{n+2}-1}{8}$$ Then I want to compute $S \mod 1000000007$. But if $n$ is a large number, it’s really hard for me to compute it. The only […]

Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$?

How to find the remainder using Fermat’s little theorem? Fermat’s little theorem states that if $p$ is prime and $\operatorname{gcd}(a,p)=1$,then $a^{p-1} -1$ is a multiple of $p$. For example, $p=5,a=3$. From the theorem, $3^5-1 -1$ is a multiple of $5$ i.e $80$ is a multiple of $5$. Similarly, I need to find the remainder when […]

How to find the quotient group $Z_{1023}^*/\langle 2\rangle$?

When $m=1023$, what are the quotient groups below? $$Z_m^*/ \langle 2\rangle$$ $Z_m^*=\{1,2,4,5, \dots \}$ $\langle 2\rangle=\{1,2,4,8,16,32,64,128,256,512\}$ $$\begin{align*} Z_m^*/\langle 2\rangle &=\{1,2,4,8,16,32,64,128,256,512\},\\ {} & \mathrel{\hphantom{=}}\{2,3,5,9,17,33,65,129,257,513\}, &&\text{(added by 1)},\\ {} & \mathrel{\hphantom{=}}\{3,4,6,10,18,34,66,130,258,514\}, && \text{(added by 2)},\\ {} & \mathrel{\hphantom{=}}\{5,6,8,12,20,36,68,132,260,516\}, &&\text{(added by 4)}\\ & \,\, \vdots \end{align*}$$ Are the answers $\langle 2 \rangle$ incremented by all the elements i$\in […]

Do inequations exist with congruences?

Gauss introduced the $\equiv$ symbol because congruences modulo $n$ were very similar to equality. But, by curiosity I would like to know if it was possible to write inequations such as: $$3x + 2y \leq 5 [7]$$.

Last two digits of $17^{17^{17}}$

For a problem set, we had two find the final two digits of 17^17^17 So what I did was find the last digit of 17^17 and then take 17^of that last digit of 17 and then find the last two digits of that number. I got the last two digits as 17. Is my method […]

How does one prove that $(2\uparrow\uparrow16)+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: $$F_1=2+1\to prime$$ $$F_2=2^2+1\to prime$$ $$F_3=2^{2^2}+1\to prime$$ $$F_4=2^{2^{2^{2}}}+1\to ?$$ And so on. Amazingly, it has been found that $F_1$ through $F_{15}$ to […]

Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

$$x\equiv a \pmod {100}$$ $$x\equiv a^2 \pmod {35}$$ $$x\equiv 3a-2 \pmod {49}$$ I’m trying to solve this system of congruences, but I’m only familiar with a method for solving when the mods are pairwise coprime. I feel like there ought to be some simplification I can make to reduce it to a system where they […]

If $\gcd(a,b)=1$, is $\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}$?

If $\gcd(a,b)=1$, is it true that $$\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}\;?$$ I know that $a^{\gcd(x,y)}-b^{\gcd(x,y)}\mid a^x-b^x$ and $a^{\gcd(x,y)}-b^{\gcd(x,y)}|a^y-b^y$, so I thought of something like let $n$ be a divisor of $a^x-b^x$ and $a^y-b^y$, then $n$ must also be a divisor of $a^{\gcd(x,y)}-b^{\gcd(x,y)}$ but I am stuck.

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 ?

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