0
votes
2answers
35 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
2
votes
0answers
93 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
1
vote
4answers
50 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 ...
1
vote
2answers
58 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
-1
votes
1answer
36 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
0
votes
1answer
70 views

Find the largest integer $n$ such that $10^n$ divides $10^6!$

Let $N=10^6!$ Find the largest integer $n$ such that $10^n$ divides $N$. Furthermore, compute the first digit and the last non-zero digit of $N$. I have some ideas that you should be able to use ...
1
vote
1answer
69 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
1
vote
2answers
73 views

Solving $x^2 + 96=0$ in $\mathbb{Z}_{100}$

I'm trying to find all solutions to $x^2 + 96=0$ in $\mathbb{Z}_{100}$. $x^2 + 96 \equiv 0 \bmod 100$ implies that $x^2 + 96 \equiv 0 \bmod 2$ and $x^2 + 96 \equiv 0 \bmod 5$. $$x^2 + 96 \equiv 0 ...
1
vote
2answers
35 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
1
vote
2answers
55 views

Show that there exists no integer coordinates on curve

Problem: Show that there does not exist any integer coordinates to the curve $$y = \frac{x^2-3}{4}, x\in \mathbb{R}.$$ My attempt: The problem is equivalent of saying that there does not exist any ...
0
votes
1answer
39 views

The addition table for $\mathbb Z/4$ - modular arithmetic

"Write down the addition table for $\mathbb Z/4$ " Could someone please give one or two hints? And what does them mean with $\mathbb Z/4$? They have never used that notation before. Do them just mean ...
1
vote
0answers
67 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
0
votes
1answer
28 views

Finding discrete maps with prescribed cycle-structure (functional digraph-structure)

I apologize in advance for the naive nature of the following questions. I am also thankful to suggestions for improving the direction of the questions instead of direct answers. Let $f: \mathbb N \to ...
-1
votes
3answers
62 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
4
votes
3answers
599 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
4
votes
0answers
32 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
122 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
66 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
38 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
20 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
1answer
88 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
45 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
47 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 ...
3
votes
0answers
40 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 ...
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
136 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
3answers
180 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
140 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 ...
2
votes
2answers
76 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
455 views

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd \pmod n$.

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd pmod n$. I tried to use $(a-c)(b-d) = ab-ad-cb+cd$, but it seem doesn't work.
1
vote
1answer
84 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
63 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
38 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
38 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
25 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
54 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
69 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
129 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
45 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 ?
2
votes
1answer
71 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 ...
1
vote
1answer
56 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$ ...
-1
votes
1answer
67 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
29 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
82 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
87 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: ...
19
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
33 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 ...