Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

0
votes
1answer
34 views

Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ ...
2
votes
1answer
27 views

How do I calculate the number of times angle X should be added to obtain angle Y?

Suppose I have a angle X=100 and angle Y=60. when we add X 15 times it gives ...
2
votes
3answers
129 views

Modular Arithmetic - Quadratic Solutions Problem

I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out. ...
1
vote
4answers
174 views

Finding remainder when $32^{32^{32}}$ is divided by $7$

I recently learnt modular arithmetic for finding remainders when huge numbers are to be divided by some number. However, I am stuck at this problem: What is the remainder when ...
1
vote
2answers
47 views

Modular Arithmetic - Finding the smallest possible length of the room in inches

I need to know if I've done this proof correctly. Question: A rectangular room is to be tiled with square tiles. Consider only the length of the room. The tiles are available in 9-inch, 10-inch, or ...
0
votes
1answer
62 views

A question on GCD

Let $n_2>n_1>r>1$ be positive integers, let $r\neq gcd(n_i,r)=t>1$ for $i=1,2$ and let $n_1\nmid n_2$. How do you disprove $gcd(n_1,n_2) \bmod r=gcd(n_1\bmod r,n_2\bmod r)\bmod r$? Does ...
1
vote
1answer
470 views

Modular exponentiation with Chinese Remainder Theorem

I'm learning modular exponentiation with Chinese remainder theorem. I found a great answer from below ...
2
votes
2answers
117 views

Clarify a problem with prime and composite numbers

What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer? The solution listed says The requested number $\mod {42}$ ...
1
vote
1answer
28 views

Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
0
votes
2answers
31 views

Combining divisibility with congruences

If we assume that $x^2 - xy + y^2 \equiv 0 \pmod n$ Then $x^2 + y^2 \equiv xy \pmod n$ If $(x,y,n)=1$. Then we can observe that neither x nor y can divide the ...
1
vote
3answers
54 views

Multiplying modulo 20

For a positive integer $n \ge 2$, define $U(n)= \{k \in \Bbb Z_n $| gcd$(k,n)=1\}$. Then $U(n)$ is a group under multiplication modulo $n$. Find the order of $U(20)$. Is it possible to generate ...
2
votes
6answers
195 views

$9999\ldots 9 \cdot 9999\ldots 9$ will always end with $1$?

Will a number consisting of only the digit $9$, multiplied with another number consisting of only the digit $9$, always result in a number that ends with $1$, and how can one know that this will ...
1
vote
1answer
56 views

GF(113) arithmetic using tables?

I need to work with the Galois Field of (prime) characteristic 113. I am wondering if it is possible to implement multiplication and division using log/antilog tables (like I already do in different ...
1
vote
1answer
48 views

modulo division of inverse numbers

I am working on some modulo arithmetic and I do not seem to understand why $28^{-1} (mod59)= 19 (mod59)=55$ is and not $28^{-1} (mod59) = 0.0035 (mod59)$ ? When I try to calculate this in Java it ...
-1
votes
3answers
133 views

Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively.

a. Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively. The three congruences are $ x \equiv 1 $ (mod 7) $ x \equiv 2 $ (mod 8) $ x \equiv 3 $ (mod 9) ...
0
votes
1answer
205 views

Modular Arithmetic - Pirate Problem

I was reading an example from my book, and I need further clarification because I don't understand some things. I'm just going to include the $f_1$ part in full detail because $f_2$ and $f_3$ are ...
1
vote
1answer
59 views

Applying the Chinese remainder theorem

I am trying to apply the Chinese remainder theorem to obtain the unique solution modulo $10^n$ for $N\equiv 1 \pmod {2^n}$ and $N\equiv 0 \pmod {5^n}$. I have reason to suppose that the solution is ...
4
votes
1answer
145 views

remainder of the division of $7^{1203}$ by $143$

I have to find the remainder of the division of $7^{1203}$ by $143$. I thought that I could use the Euler Theorem: Let $a \in \mathbb{Z}$ and $n \in \mathbb{N}$.We also know that $(a,n)=1$.Then ...
1
vote
0answers
65 views

Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$. $P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from ...
3
votes
5answers
350 views

Modular Arithmetic - Are we allowed to distribute the Modularity?

Assume I have a problem such as "Prove that $\displaystyle103^{53} + 53^{103}$ is divisible by $39$." This would mean I wanted to prove that $\displaystyle103^{53} + 53^{103}\equiv0\pmod{39}$. My ...
2
votes
3answers
56 views

Why do put at $k$ only values from $0$ to $6$

Find an integer $x$ whose remainder of the division with $10$ is $3$ and the remainder of the division with $7$ is $4$. $$x-3=10k \text{ and } x-4=7l$$ From the first equation we get: $ x=10k+3$. ...
8
votes
6answers
429 views

Fermat's Little Theorem: exponents powers of p

I was working with congruence classes and encountered Fermat's little theorem: $$a^{p } \equiv a \mod p$$ But I noticed that a$^{p^{k}} \equiv a \mod p$. I used induction on $k$ but I'm still not ...
1
vote
0answers
112 views

Why doesn't this base 10 number x mod 2^y work for converting base 10 to binary

Okay I tried to convert 1 million to binary by dividing by a power of 2 and taking the remainder and dividing that by a power of 2 and so on and I got this: 1111010000100100000 Google says 1 million ...
2
votes
1answer
74 views

Abstract Algebra Computation

Compute: $3^{47}$ mod $23$ $3^{49}$ mod $7$ $2^{2^{17}}$ mod $23\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ hint: compute first $2^{17} + 1$ mod $19$ This is the first time I've had to ...
2
votes
2answers
70 views

Is the fact that if $x \equiv a\:mod\:b$ then $x^n \equiv a^n\:mod\:b$ also true in reverse?

I'm trying to solve the following question: Show that If $x^2 \equiv x\:mod\:p^k$, then $x \equiv (0\:or\:1)\:mod\:p^k$ where $p$ is prime and $k$ is a positive integer. I've managed to get as far ...
0
votes
1answer
75 views

How is 4 a quadratic residue of 7?

On Wolfram's dictionary, it shows that the quadratic residues of 7 are 1,2,4. It shows that the quadratic residues of 5 are 1,4. I tested 1 and 4, and as you can see: $$1^2 = 1 \pmod 5$$ and $$ 4^2= ...
0
votes
2answers
41 views

Prove that this equation have an non finite number of prime solutions

So the question seeks to answer the following, let $x,y\in\Bbb R$. Prove that there is a non finite number of prime solutions to the following equation: $3x-5y=11$. Our professor says that it's easy ...
0
votes
1answer
50 views

$x_i=x_{i-1}^2+a\pmod{N}$ with $N$ a composite number.

$x_i=x_{i-1}^2+a\pmod{N}$, $N$ is an odd composite number, assume $N=p \cdot q$ with $p,q$ primes, $x_0=1$ then calculate $\gcd(x_i,N)$, for what $a$ the quadratic iterative function give one factor ...
0
votes
2answers
49 views

Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
2
votes
2answers
527 views

Hint for finding the remainder when $2018^{2019}$ is divided by 13

I have been thinking of how to answer this. The question is find the remainder of: $$\frac {(2014^{2015}) \space (2016^{2017}) + 2018^{2019} \space}{13}$$ This is what I was thinking: Since $ 13 ...
0
votes
3answers
42 views

Solving linear modular equations

How does $17r \equiv-2 \pmod {11} $ reduce to $r\equiv-4 \pmod {11}$? I know that $-2\equiv9 \pmod {11}$, but how do I simplify the $17$?
0
votes
2answers
49 views

Modular arithmatic, basic question [closed]

How does this: $2x + 3 \equiv -1 \pmod {10}$ directly lead to this: $2x = 6 \pmod{10}$
0
votes
1answer
63 views

Proof that $x^n \mod b = (x \mod b)^n$

I've been messing around with modular arithmetic recently, and stumbled across this, but couldn't find a proof for it anywhere. I hate taking things as truth without knowing why, so could anyone ...
4
votes
0answers
139 views

Solving $x^e\equiv a\pmod n$

I am trying to put together the techniques involved in solving $$x^e\equiv a\pmod n, \text{ for known } n\in\mathbb N^*, e\in\mathbb N^*, a\in\mathbb Z_n, \text{ unknown }x\in\mathbb Z_n$$ I'm ...
0
votes
1answer
149 views

$a ≡ b $(mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$)

Verify that if $a ≡ b$ (mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$), where the integer $n = lcm(n_1 , n_2)$. Hence, whenever $n_1$ and $n_2$ are relatively prime, $a ≡ b$ (mod ...
46
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
3
votes
3answers
35 views

Sum of powers of $2$ modulo $11$: $\sum_{i=0}^{5 \cdot x -1} [2^{4i}] \equiv 0 \mod 11$

I tried the proof by reducing the exponents modulo 10, but didn't really get a solution :/. Would love some help :D, thanks guys
3
votes
1answer
53 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
0
votes
1answer
90 views

Integers $p,q$ such that $pq\equiv 1 \mod (p+q) $

I want to find pair of integers $p,q$ of the form: $$pq\equiv 1 \mod (p+q) $$ What have I tried so far is: Since, $pq \equiv 1 \implies p$ has inverse element with respect to $p+q$. which means ...
-1
votes
5answers
80 views

If $x \equiv 1 \pmod 3$ and $x \equiv 0 \pmod 2$, what is $x \pmod 6$? [closed]

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?
1
vote
0answers
72 views

If $x=1\mod3$ and $x=0\mod2$, what is it $\mod6$? [duplicate]

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?
0
votes
1answer
98 views

Show that the mod p map is a ring homomorphism

Let p be a prime and let (mod $p$)$ : Z[x] \mapsto Z_p[x]$ be the mod-p map which sends any polynomial... $f(x) = a_0 + a_1x + a_2x^2 + · · · + a_nx^n \in Z[x]$ ... to the polynomial... $f(x)$(mod ...
1
vote
1answer
53 views

$a$ modulo ${\prod_{i}p_i}$ where $p_i$ are primes.

This may be a very simple question for many of you. But somehow I can not see how to find a good way to answer this. The question is that if it is given that $$a\equiv k_i\mod{p_i},\quad ...
1
vote
2answers
48 views

Modular arithmetic question related to the fundamental theorem

Somewhat of an unusual homework problem that my professor assigned that I can't wrap my head around. We are only considering the positive numbers congruent to 1(mod 4), that is, other numbers do not ...
0
votes
2answers
32 views

Modular arithmetics

I am having a question specific for this video on Youtube: https://www.youtube.com/watch?v=3QnD2c4Xovk They seem to explain that shared encryption concept pretty well, but I seem to get some incorrect ...
0
votes
1answer
353 views

Modular multiplicative inverse in RSA

I been reading the wiki article about Modular multiplicative inverse and I don't understand it. Can you explain it to me in better way. To be more specific I am trying to understand the RSA algorithm ...
0
votes
2answers
85 views

Big O for modular exponentiation?

I am reading the Algorithms textbook by Dasgupta, Papadimitriou and Vazirani. To compute x^y mod N for large values of x y and N, they state: "To make sure the numbers we are dealing with never grow ...
1
vote
1answer
61 views

cost and price profitability analysis

I have been struggling with this question for a long time, Is there somebody kind enough to help? If I received 1 free unit for 3 units purchased, how many units should I sell to issue 1 free unit? ...
0
votes
2answers
51 views

Solving a modular equations system

I'm trying to solve the following eqution: $ \left\{ \begin{array}{l l} 5x (mod \space m) = 7\\ 7x (mod \space m) = 5 \end{array} \right. $ for $x$ and $m$. (this is a part from a ...
1
vote
3answers
164 views

How do you calculate a large power modulo a small number? [duplicate]

How do I calculate $12345^{12345} \operatorname{mod} 17$? I cant do it on a calculator? How would I show this systematically?