2
votes
2answers
59 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
23
votes
2answers
838 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
4
votes
3answers
575 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?
6
votes
3answers
69 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
0
votes
0answers
25 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
0
votes
0answers
24 views

Taking the modulus of the power?

So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
0
votes
2answers
47 views

Find the smallest possible integer $k$ such that $8|7^{348}+2^{5605}+k$

$$ \text{Find the smallest possible integer } k \text{ such that } \\ 7^{348}+2^{5605} +k \text{ which is divisible by } 8 \text{ given that } $$ a≡b mod n⇒a^m≡b^m mod n okay, I understand that $a ...
1
vote
1answer
42 views

Show that $gcd(a,b) |d $ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d $ and hence $\gcd(a, b) \leq d$
1
vote
4answers
121 views

What's the easiest way to factor $5^{10} - 1$?

What's the easiest way to factor $5^{10} - 1$? I believe $5 - 1$ is a factor based off the binomial theorem. From there I do not know. We are using congruence's in this class.
2
votes
1answer
55 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
0
votes
1answer
36 views

Help with understanding Induction proofs

From my understanding, to prove induction problems, we must: Find a base case Assume n=k holds true Prove n=k+1 with the assumption However I am looking at the proof of a problem and they don't ...
0
votes
1answer
51 views

Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
3
votes
3answers
104 views

how to prove if $m^{2}|n^{2}$ then m|n just hint please. [duplicate]

How to prove the following?: Let $m,n\in \mathbb{N}$ ; $ \;m^{2}\mid n^{2}\Longrightarrow \;\;m\mid n$ Just a hint please. I tried two ways but did not work.
0
votes
1answer
68 views

An easy question with integer numbers

I have an easy question of arithmetic. Let $a, b, N$ be integer numbers such that $\mathrm{gcd}(a,b,N) = 1$. Is it true that there exists an integer number $x \in \mathbb{Z}$ such that ...
2
votes
2answers
113 views

Prove that if $a$ is irrational then $\sqrt a$ is irrational

Just hints but solution thx. Any hints for me? I simply suppose that $a = \dfrac mn$ then $\sqrt a = \sqrt{\dfrac mn}$ But this does not make sense ..
3
votes
1answer
40 views

$k$th difference of $1,2^k,3^k,…$

I read, in an exposition of Euler's proof of Fermat's theorem on sums of squares, that the $k$-th order finite forward difference of the function $f(x_i)=x_i^k$, relatively to the nodes $x_i=i$ where ...
0
votes
2answers
75 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
1answer
83 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
0
votes
1answer
34 views

showing that encryption method is bijective

A encryption method relates a letter Ω to letter $Δ\equiv aΩ + d$ $(mod 30)$ with $a, d\in {\Bbb N}$. Each letter relates to a number: A = 01, B = 02, C = 03 ... i. Show, that this encryption method ...
1
vote
3answers
105 views

Greatest common divisor. Help

Let $n \in \mathbb{N}$. Prove that $$\gcd(2^n+7^n;2^n-7^n)=1$$ $$\gcd(2^n+5^{n+1};2^{n+1}+5^n)=3\text{ or }9$$
1
vote
8answers
145 views

How to find all the positive integral solutions of $5x+7y=100$?

How to find the number of all the positive integral solutions and the solutions itselves of $$5x+7y=100?$$ Please help me!!
1
vote
1answer
40 views

Sum of floor of rational product

Given natural numbers $a,b,n$, where $a<b$, $n<b-1$, and $a$ and $b$ coprime, Find a closed form for the sum: ${\displaystyle \sum_{k=1}^n \left\lfloor k \frac{a}{b} \right\rfloor}$ We know ...
9
votes
5answers
217 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
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 ...
2
votes
4answers
55 views

Find the smallest positive $n$ such that $n! \equiv 0 \pmod {425}$

By exhaustion I found $n=17$, but in trying to solve this I can only see that: $$425\space |\space n!\space \longrightarrow\space 425k=n!$$ Any hints?
1
vote
2answers
35 views

Prove $a,b \in \mathbb{Z}; p, q \in \mathbb{Z^+}$: If $a \equiv b \pmod{pq}\space \longrightarrow \space a \equiv b \pmod p$

$pq|a-b$ and $p|a-b$ $pql = a-b$ and $pk=a-b$ Let $k=ql$ then, $pql = pk=a-b$ First, is this correct? Second, if so, why can we let $k=ql$? How do we know $ql=k$?
1
vote
1answer
111 views

Diophantine equation $11\cdot 2^y-3x^{10}=2014$

Ok so I have a trouble figure out here For the Diophantine equation $11\cdot 2^y-3x^{10}=2014$, either find all integer solutions, or show that there are no integer solutions.
0
votes
1answer
45 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
1
vote
1answer
39 views

Uniqueness proof of binary representation

I'm having trouble understanding this proof of uniqueness of binary representation of integers: Suppose there exists an integer $n$ with two different binary representations. Let these be: ...
1
vote
6answers
233 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
37
votes
6answers
3k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
1
vote
4answers
368 views

How many Positive integer solutions does the equation $x + y + z + w = 15$ have?

How many Positive integer solutions does the equation $x + y + z + w = 15$ have? Attempt: Let $x = m + 1, y = n + 1, z = o + 1, w = p + 1 $ Then, $ m + 1 + n + 1 + o + 1 + p + 1 = 15$ $ m + n + ...
0
votes
3answers
46 views

Find GCD $(10^6\times 6^2 \times 5 ; 6 \times 15 \times 3^7)$

Find GCD $(10^6\times 6^2 \times 5 ; 6 \times 15 \times 3^7)$ I have no idea.
0
votes
2answers
68 views

Solution to $x^2$ mod $23=7^2$ [duplicate]

Recently, I stumbled upon this problem, Solve $x^2$ $mod$ $23 = 7^2$, both here at MSE and somewhere surfing the web. I tried to solve it but don't know how. Although I can't remember where I found ...
2
votes
5answers
340 views

How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?
7
votes
9answers
1k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
0
votes
0answers
43 views

solve some discrete mathematic problems

(a) Solve for $x$ , $2x \equiv 5 \pmod 9$ (b) Prove that for any integer $a$, $a^2 \equiv 1 \pmod 4$ or $a^2 \equiv 0 \pmod 4$. (c) Prove that $a × b = \text{lcm(a, b)} × \text{gcd(a, b)}$ (d) ...
0
votes
1answer
98 views

Proving number of digits d to represent integer n in base B?

I am interested in learning about proofs for discrete mathematics. One recurring fact I find in the literature is that the number of digits $d$ required to represent integer $N$ in base $B$ is ...
0
votes
3answers
42 views

If s=∅ , T≠∅ then SxT = ∅ . Why? [duplicate]

I recently studied about Cartesian products and I thought that I understood its concept, Until I ran into this expression: If $S=\emptyset$, $\ne\emptyset$, then $S\times T = \emptyset$ . Is an ...
1
vote
1answer
96 views

For what values of m does the equation 35530x + 355y = m have integer solutions?

For what values of $m$ does the equation $35530x + 355y = m$ have integer solutions? (only find the $m$'s for which solutions exist)
0
votes
5answers
99 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
1
vote
1answer
51 views

Remainder Question

What process do I use to show what is the remainder when 14 × 7^36 + 92 when divided by 8? Is it the same to show the remainder of ...
1
vote
1answer
35 views

on roots of an equation

Let $A=\{0,1,\cdots,d-1\}$. Consider the set $P(n)=\{(x,y)\in A\times A:x+y=n\}$. Consider the function $F(X)=\sum_{n=0}^{2(d-1)} \# P(n) X^n$, where $\#$ denotes the cardinality of $P(n)$. For the ...
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$ ...
1
vote
3answers
52 views

If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement: Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common ...
0
votes
1answer
30 views

How to calculate the rest of $2^{p^r-p^{r-1}+1}$ divided by $p^r$

I have the next problem: $p$ is an odd prime number and $r$ is a natural number, $r>1$. How can I calculate the rest of the division of $2^{p^r-p^{r-1}+1}$ by $p^r$ ?
0
votes
1answer
277 views

Discrete math question - Fibonacci sequence

Fibonacci sequence is embedded in Pascal’s triangle by investigating “stretched diagonals”. While this is true, it is not obvious how the sequence is embedded. Redraw Pascal’s triangle to make it ...
1
vote
6answers
102 views

Proving $n! < n^n$

I have to prove $n! < n^n$ for positive integers greater than 1, but with a little twist. I have to show $P(n-1)$ holds. For the left, I know $(n-1)! = \frac{n!}{n}$ and I'm stuck from there ...