4
votes
3answers
574 views

Proof about prime numbers

Can we prove that every prime larger than 3 gives a remainder of 1 or 5(edited) if divided by 6 and if so, which formulas can be used while proving?
4
votes
0answers
25 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
0
votes
1answer
67 views

Solving mod congruence

So i have a problem like this 34x ≡ 77 (mod 89) This is how i try to solve it but it doesn't seem to work :( If anyone can give me a hint on how to proceed from ...
0
votes
3answers
49 views

Discrete mathematics. Just an impression, or this is always true?

I feel that the following is always true: $$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \text{ if }k \equiv 0 ~(\text{mod }2) \wedge k \geq 2$$ I've just tried it using a "brute force" approach, but ...
1
vote
1answer
30 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...
0
votes
1answer
8 views

Calculate power of large numbers mathematically?

Is there a short-hand method to find the value of a number with a large power. For example : 1024^2048
0
votes
0answers
21 views

How to find p such that 1/p has a repeating decimal with a specified period

Alright, so I know a bit of information about the problem but I'm having trouble tying it all together. I know: if gcd(n,10)=1 then 1/n has a repeating decimal expansion. 10^3 = 1 mod p 1/p = ...
0
votes
1answer
53 views

Convert modulo 65 into modulo 26.

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?
1
vote
1answer
40 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 ...
0
votes
2answers
46 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 ...
1
vote
0answers
30 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've good basis of mathematical analysis ...
2
votes
1answer
55 views

Show that for all natural $a$, $2008\mid a^{251}-a$.

How to show, that for all natural $a$ coprime to 2008 the following occurs: $2008\mid a^{251}-a$? This means, that $a_{251} \equiv_{{}\bmod 2008} a$, right? It's obvious if $a\mid 2008$. In the ...
2
votes
2answers
122 views

Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1.

The question is: Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1. The answer is 441. What I did when I tried solving this was to set up 3 ...
0
votes
2answers
79 views

Book on modular arithmetic

I am searching for some good book which section is devoted to modular arithmetic. I am self learner so I strongly prefer that book has exercises best with answers or solutions. I have CS background ...
0
votes
5answers
81 views

$4011x+42053 \equiv 2x-782398 \pmod {10}$

$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
4
votes
4answers
121 views

Solve $x^2+x+3=0$ mod $27$

I was preparing for my Number Theory class for next semester and one of the questions that I came upon is to solve $x^2+x+3=0$ mod $27$. I have seen modular arithmetic before but never one that ...
3
votes
2answers
74 views

Is the following always True?

Let $a, b \in Z$ and $n \in N$ . Is the following necessarily true? If $a^3 ≡b^3$(mod n) then $a ≡ b$ (mod n) How do I do this? For the record, I do not think this is True.
0
votes
3answers
259 views

Prove if a≡c (mod n) and b≡d (mod n) then ab≡cd (mod n)

Prove if a≡c (mod n) and b≡d (mod n) then ab≡cd (mod n). I tried to (a-c)(b-d)=ab-ad-cb+cd, but it seem doesn't work.
1
vote
1answer
47 views

Minimum number of rows in a mod 12 multiplication table

Minimum number of rows you would need to write out in a mod 12 multiplication table to guarantee you wrote out an element with an inverse? I would think this would be just one row as 1 is its own ...
-1
votes
1answer
55 views

UPC code proof help

i'm trying to prove the following problem.. 1. Prove that if a single digit of a valid UPC is changed then the new code is not valid. Answer - When the question ...
0
votes
2answers
32 views

Congruence equation proof

Proof that $\forall{a}\in\Bbb N \rightarrow a^3\equiv a\mod (a+1)$ I do not know how to prove these equations. I only know that $a\equiv m \mod b \implies m | ( b- a ) \implies b-a=m\times k $ for ...
2
votes
3answers
31 views

Congruence equation problem

My problem says: Give solution to this problem of congruence, with all incongruent solutions according to the requested module and all integer solutions. $10x \equiv 15 \mod 35$ But I can not ...
1
vote
1answer
21 views

Solving linear congruences

I am trying to solve $25x\equiv15\pmod{29}$ I multiply both sides by $7$ which makes the L.h.S congruent to $1x \pmod{29}$ From this I have that $7\times25x\equiv7\times15\pmod{29}$ I am really ...
0
votes
2answers
53 views

Modular Arithmatic

I have been struggling with modular arithmetic, and I would like to try and finally grasp the concept. In particular, solving problems like $7^{30}$ mod 49. I know I will have to use Fermat's Theorem ...
2
votes
1answer
44 views

Recursive Function - mod 5

How do the recursive function for $\mod 5(x) = 0$ rest of division of $x$ by $5$. $$\begin{align} \mod&5(5) = 0\\ \mod&5(6) = 1\\ \mod&5(7) = 2\\ \mod&5(8) = 3\\ \mod&5(9) = 4\\ ...
0
votes
1answer
78 views

How do you solve linear congruences with three variables.

Given \begin{cases} x+y+z &\equiv 1 \pmod{10} \\ x+2y+3z &\equiv 2 \pmod{10} \\ 2x+3y+6z &\equiv 3 \pmod{10} \end{cases} find $x,y,z$. How does one solve such a system of ...
0
votes
1answer
40 views

The closed form of a sum of mod(k,m) where k goes from 1 to a arbitrary number.

Is there a closed form for $\sum_{n=0}^{C} mod(n,m)$ for arbitrary integers m ?
1
vote
1answer
64 views

Proof related with prime numbers and congruence

How to (dis)prove this $ (n-2)! \equiv 1 \mod n$ If n is said to be a prime number. I guess we'll have to use FERMAT’S LITTLE THEOREM, and I just don't know where to start from. Thanks in advance ...
0
votes
1answer
55 views

Proofs related with odd numbers and modulo 8

In my problem I have $ s! + s^{2P} \equiv 1 \mod 8$ where $s > 4, P \geq 1, s,P \in \mathbb{Z}^+$ I tried to follow that example's logic, but I could not get a result $n^2 \equiv 1 \mod 8$ ...
-2
votes
1answer
64 views

prime number related proof

I want to prove if following is true for every integer a,b and c $$a^2 - b^2 = cp $$ then p|(a+b) or p|(a-b) where p is a prime number. Any suggestion, help would be highly appreciated. Thanks ...
0
votes
1answer
54 views

What is the identity for ab=2ab (mod 7)?

Using elements 1, 3, 5 write out a Cayley table. The operation for the table is ab = 2ab. For example 5*4= 5*4*2= 40 congruent to 5 (mod 7). What is the identity for this table?
0
votes
2answers
28 views

Smallest integer x s.t. x! congruent to 0 (mod 216)

By guess and check I found x to be 9, but is there a more general way to solve this?
1
vote
2answers
73 views

Find the smallest integer x s.t. x congruent to 1 (mod 1,2,3,4,5,6,7,8,9,10)

Don't really understand this question. If this is asking to find an x for each mod then the answer would be just be x+m...If this is asking to find an x that satisfies all mods, then this cant be ...
0
votes
1answer
78 views

Modular arithmetic and one-to-one functions

Let $S = \{0, 1, 2, 3, · · · , 99\}$ . For each of the following functions $f : S \rightarrow S$ , determine whether it is one-to-one and onto, by computing its values for all $k ∈ S$: Function 1: ...
17
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
0
votes
2answers
45 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
1
vote
1answer
32 views

How come when $2^{k} | (x-1)(x+1)$ one of the terms is divisible by $2$ and not by $4$ when $k \in \mathbb{N} $ and $3 \leq k$

So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$. So other cases (when $p$ is an odd prime or ...
0
votes
1answer
36 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...
4
votes
2answers
56 views

Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$? I thought that I will find it piece by piece with help ...
0
votes
0answers
42 views

Must the “n” in mod(n) always be prime?

I'm experimenting with mod(n) and have the following questions even after reading the Wiki page and numerous articles about the subject. Must mod(n) always be prime for cryptographic purposes? Is ...
1
vote
0answers
65 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
3
votes
4answers
159 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
1
vote
2answers
122 views

Extended euclidean algorithm

So I am trying to figure this out. And for one of the problem the question is x*41= 1 (mod 99) And the answer lists ...
0
votes
4answers
72 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
1
vote
1answer
40 views

using Gauss' algorithm (for linear congruences) for A > B

To solve $Bx \equiv A \pmod{m}$, use Gauss' algorithm. The algorithm works perfectly when $A < B$. For example, to solve $6x \equiv 5 \pmod{11}$: $$x \equiv \frac{5}{6} \equiv \frac{5(2)}{6(2)} ...
3
votes
1answer
468 views

Finding multiplicative inverse modulo n using matrix method

According to this video (15:17 onwards), there is a "matrix method" to find the multiplicative inverse of $a$ mod $n$ by row reducing $$\begin{bmatrix} a & 1\\ n & 0 \end{bmatrix}$$ In the ...
-1
votes
1answer
46 views

Question about modular arithmetic proofs

I'm having trouble with the following proof: For any integer x and any integer k, x (mod k) = x. Can anyone help with this?
2
votes
1answer
144 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
0
votes
1answer
52 views

how to work out $14^{293}-12^{26}\pmod{13}$

How can I work this out without a calculator? $$14^{293}-12^{26} \pmod{13}$$ I just couldn't figure out a way to do this.
1
vote
1answer
156 views

Homework problem on identifying a sequence

I had this problem in my discrete math/modular arithmatic course where I had to find the first 10 terms of a series F(r), starting from F(3). The given information is: F(3)=1 F(4)=13 F(10) % ...