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

2
votes
2answers
60 views

How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

How can i prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?
1
vote
0answers
35 views

Standard form for partitions of $Z_n$

Let $A$ and $B$ be partitions of $Z_n$. Let's say that $A$ and $B$ are equivalent if $A=Bx+y$ for some $x\in{1,−1}$ and $y\in Z_n$. In other words, two partitions are equivalent if one can be obtained ...
3
votes
3answers
58 views

Finding all solutions for to the equation $x^3 = 0\ {\rm mod}\ 9$

How do I go about finding the solutions to: $$ x^3 = 0\mod 9 $$ Any help is greatly appreciated thank you
5
votes
5answers
338 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
2
votes
2answers
61 views

Chinese Remainder Theorem RSA

I want to solve the following modular quadratic equation: $x^2 \equiv 188 \pmod {437}$ using the fact that $437$ can be factorized by the primes as: $19⋅23$. So far I have done: $$x^2 \equiv 188 ...
0
votes
1answer
27 views

Vector spaces and bases

Let $F_p = Z/pZ$ be the fi eld with p elements for some prime p, and consider the vector space $V = F^3_p$ over $F_p$. Find an ordered basis for V containing the element $(1; 1; 1)$. How does ...
4
votes
1answer
56 views

Number of answers of equation amongs odd natural numbers

How many answer The following Equation has, in set of odd natural numbers? $x_1+x_2+...+x_k=n$, $k \equiv^2 n$ Solution: Comb ( [(n+k)/2]-1, k-1), comb means combination. how we get this?
2
votes
2answers
27 views

Sum modulo a prime

Simple question to which I expect a not so simple solution/proof. Let $p$ be a prime and choose n numbers randomly from $\mathbb{Z}/p\mathbb{Z}$ using the uniform distribution. What is the ...
-1
votes
1answer
43 views

A set S contains 9^1, 9^2, 9^3, … , 9^8 where the operation is multiplication modulo 64…

Doing some practice for sets and groups, when this question has me absolutely stumped! The set S consists of the eight elements 9^1, 9^2, 9^3, ..., 9^8 where the operation is modulo 64. Determine each ...
-1
votes
1answer
34 views

Given a set under multiplication modulo 13, find or explain why none exists a subgroup of G with order 5 [closed]

you are given the set {1, 2, 3, 4, ... , 12} forms a group G under multiplication modulo 13. A subgroup with n elements is said to have order n. Find, or explain why none exists, a subgroup of G with ...
0
votes
2answers
43 views

Modular Arithmetic Eggs in a basket

Apologies, I know I have asked a few questions already. The question is : A housewife is travelling to market with all her eggs in one basket. She has between $100$ and $200$ eggs in the basket. ...
0
votes
1answer
39 views

euler's phi function and modular help

I can't seem to even find an example of this, so if anyone could help me with an example or how to do it (I am doing this purely for myself) it would be greatly appreciated: Use Euler's phi function ...
1
vote
4answers
25 views

Modular Arithmetic Simple question

Hi I am studying modular arithmetic just for myself, but to be honest I find it very difficult. I am not sure which answer is right. Is it right to say If $4x \equiv 8\pmod{15}$ then $x \equiv 2 ...
1
vote
2answers
79 views

Day of the week from the date.

I still remember when I was a kid some senior student used to ask us a date from history and then tell us what day was then within 20 seconds. I read montgomery's Number theory and when found the ...
1
vote
2answers
38 views

Power of very big numbers

So, I was solving a question, and I came across this. If I have, x=a^b, and If I want to calculate the last digit of x, then it ...
0
votes
1answer
15 views

Modular arthimetic congruent four distinct values

What are the four distinct values which are congruent to 6 when the base is 12? we got 1,and 4 so far but no the other two numbers
0
votes
1answer
20 views

Find a number $a$ that has the following three properties

The number 3750 satisfies $\Phi(3750) = 1000$. Find a number $a$ that has the following three properties $a \equiv 7^{3003}\bmod{3750}$ $1 \leq a \leq 5000 $ $a$ is not divisible by 7 Any help on ...
-1
votes
0answers
31 views

Modular arthimetic

What are the four distinct values which are congruent to 6 when the base is 7? I already have two of them which is 6, and 48 but i can not figure out the other two I have tried all other
2
votes
1answer
25 views

How would you solve this modular equation without being able to find the multiplicative inverse?

If I have $15a \equiv 60 \space mod \space 95$, how could I solve for $a$? The equation has multiple solutions (23 and 42 among them) -- how do I find them without resorting to guess-and-check?
0
votes
2answers
33 views

Relationship between fibonacci number and modulo. [closed]

Determine with reason whether or not $$F_{5n}=0\pmod5$$ I don't have any idea about it.
1
vote
2answers
23 views

reducing exponent in modular arithmetic

Im struggling with an example excercise because I have problemes to comprehend an step in the calculation $3^{36} \mod 59 = 3^{7} \mod 59$ How can I reduce the exponent $36$ to $7$? I tried it with ...
0
votes
2answers
42 views

Finding the remainder of a division

$75$ is the remainder of $X$ divided by $132$. What is the remainder of $X$ divided by $12$? I know the answer is $3$ but how do we get that answer?
5
votes
2answers
95 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
0
votes
3answers
41 views

Subgroup generated by and element

Consider the group G = {1, 3, 5, 7} under multiplication modulo 8. What is the order of the element 5? I know that the order of an element is the order of the subgroup generated by the element. so ...
3
votes
2answers
45 views

Proving divisibility by 7 using modular arithmetic [duplicate]

Prove that $2222^{5555} + 5555^{2222}=0 \pmod{7}$. I'm not getting how to start away with this problem. I know that modular arithmetic should be used. Please give me some hints on how to solve this ...
1
vote
2answers
39 views

An expression is divible by 4 but not 8.

Let $n\in\mathbb{N}$. Show that $4\mid(3^{2n+1} + 5^{2n})$ and $8\nmid(3^{2n+1} + 5^{2n})$ $(2m+1)^n = (2m+1)_1(2m+1)_2...(2m+1)_n$. Here I'm trying to show that an odd number raised to any integer ...
-2
votes
1answer
35 views

Question on the relationship of a quantity and its value modulo n [closed]

Is it correct to say that if there are 13 chameleons, then there are $1\pmod 3$ chameleons? If so, why?
0
votes
1answer
43 views

Fast modular exponentiation

Suppose that $p$ and $q$ are distinct primes, then for every integer $a$ and exponent $e$ with $e\not \equiv (\bmod \,(p - 1)(q - 1))$ show that: ${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - ...
0
votes
3answers
41 views

Modular arithmetic

Hello, What is the remainder when the following sum is divided by 4? $1^5 + 2^5 + 3^5 +...+ 99^5 + 100^5$ I feel like it has to do with modular arithmetic... I am trying to decompose every number ...
3
votes
2answers
30 views

What does the modulo of a non-integer mean?

For example, in the equation $ x=\frac{3}{5} \bmod 11$ The value of $x$ is $5$ according to wolfram alpha. I know how to manipulate the equation to to get the value but I dont understand what the ...
3
votes
3answers
64 views

Prove the following fraction is irreducible

Prove $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$. I was thinking of taking a number-theory based approach. Can you suggest the following method Calculus/Number theory ...
0
votes
1answer
46 views

Proof that $ax \equiv 1 \mod{n}$ has no solutions when $a$ and $n$ aren't co-prime?

Does this proof work? Is there a simpler one (precluding citing other theorems)? Suppose $ax \equiv 1 \bmod{n}$. Then $ax = kn + 1$. We have some $d = \gcd(a, n)$ such that $a = da'$, $n = dn'$, and ...
0
votes
0answers
41 views

Solving system of equations using mod math for a Hill cipher

I am having trouble eliminating these variables when I try to solve this system of equations. They may not even be the right equations, but it would be nice to see this worked out so I can try my next ...
0
votes
2answers
61 views

Find integers x and y with 103x + 113y=1

Find integers $x$ and $y$ with $103x + 113y=1$ How would you solve this problem? I'm thinking maybe you can use Euclidean Algorithm to solve for the inverse?
2
votes
1answer
101 views

The number $2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. [duplicate]

$2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. I've seen its solution before but I still don't understand it. Math novice here. A detailed answer will ...
1
vote
2answers
29 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
1
vote
0answers
53 views

[ANSWERED]Is $\{n, n^{2} n^{3}\}$ a group under multiplication modulo $m = n + n^{2} + n^{3}$?

My number theory has been lacking, so i decided to practice it a bit. I have gotten better in the sense that i can figure out where to begin approaching a problem, but i am having trouble seeing the ...
1
vote
3answers
55 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
0
votes
1answer
25 views

Explanation of congruence and modulo

Consider the set $A$ = {${-6, -5 -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12}$} Write down the numbers in $A$ congruent to $1$ modulo $4$. Can someone explain why the answer is not $-4,-1,-4,8,12$ ...
2
votes
1answer
36 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
31 views

Why is any number to the 1,5,9,13, etc. modulus 10 itself?

Why is $n^{4k+1} \% 10 = n$ for any integer $n$ and any whole number $k$? What about base 10 math makes this sop?
1
vote
0answers
10 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
0
votes
1answer
22 views

(Statistics)Probability of given sum in dice tossing [closed]

I need some help with this problem: By tossing two dice, what is the probability of: i) Total sum of 7 ii) Difference of 5 iii) Total sum multiple of 7 Thanks everyone ~Chris
0
votes
3answers
49 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
1
vote
2answers
78 views

Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

$2^{561}\equiv ? \pmod{561}$ Few observations : $561 = 3\times 11\times 17$ So Fermat's little theorem is not useful here. Any hints ? If possible, kindly avoid carmichael numbers/group theory/euler ...
0
votes
0answers
24 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
0answers
31 views

CRT Algorithm using InvMod + Undefined

I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while ...
1
vote
1answer
13 views

$A^{-1}x \pmod{26}$ and coprime requirement in Hill cipher

I am reading Hill cipher from wiki page and I have been stuck on this thought for a while. Why is there a requirement for $\det(A)$ and $26$ to be coprime in Hill cipher ? Anybody familiar with Hill ...
0
votes
1answer
50 views

Exist an explicit formula to calculate the minimum number of divisions by two that leave a rest < 0.5?

I have a number $x \in \Bbb R/\Bbb Z$ (i.e. any number but entires) and I want to know if exist a explicit formula that evade recursion to calculate the minimum n that $$\frac{x}{2^n}\mod ...
0
votes
2answers
27 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, ...