# Tagged Questions

2answers
24 views

### Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$ I have tried a few approaches, ...
0answers
33 views

### Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
4answers
32 views

### How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
4answers
52 views

### Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
2answers
87 views

### For every integer, some multiple of it is of the form $99 \ldots 900 \ldots 00$

The goal is to prove that for every positive integer $z$ there exists a positive integer $a$ such that $az = 99 \ldots 9900 \ldots 00$. Let $a = \frac {99 \ldots 9900 \ldots 00}{z}$ That ...
2answers
81 views

### Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
1answer
82 views

### Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014.
1answer
59 views

5answers
187 views

### Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
4answers
952 views