Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
3answers
33 views

Proof of divisibility: $17 \mid 3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ [on hold]

As the title says, prove that $3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ is divisible by $17$.
2
votes
1answer
25 views

Calculate $\sqrt{x^2+y^2+2x-4y+5} + \sqrt{x^2+y^2-6x+8y+25}$, if $3x+2y-1=0$

As the title says, given $x,y \in \mathbb{R}$ where $3x+2y-1=0$ and $x \in [-1, 3]$, calculate $A = \sqrt{x^2+y^2+2x-4y+5} + \sqrt{x^2+y^2-6x+8y+25}$. I tried using the given condition to reduce the ...
1
vote
1answer
16 views

Divisibility: $60 \mid (2x-y)(2y-z)(3z+2x)$, if $8x-10y+27z=0$

As the title says, given $x,y,z \in \mathbb{Z}$, where $8x-10y+27z=0$, prove that $(2x-y)(2y-z)(3z+2x)$ is divisible by $60$. I tried to bring the formula in a format of $(\cdots)(8x-10y+27z) + ...
0
votes
1answer
35 views

Find $n$ such that $209$ divides $n^{180}-n^{20}-n^{36}+1$

Finding $n\in \mathbb{N}$ (with $n > 1$) such that $209$ divides $n^{180}-n^{20}-n^{36}+1$ is equivalent to solving $$ n^{180} - n^{20} - n^{36} + 1 \equiv 0 \mod 11 \quad \text{ and } \quad ...
2
votes
1answer
20 views

Find all elements of multiplicative order 18.

Find all elements of $\mathbb{Z}_{19}^*$ of multiplicative order $18$. I started by using Euler's Theorem and since gcd(18, 19) = 1 it implies that $a^{\phi (19)} \equiv 1 \pmod n$. Which means ...
2
votes
2answers
35 views

Is there an easy way to check whether or not $3$ divides a number that is written in decimal notation?

(Convention. I include $0$ in the natural numbers, i.e. $0 \in \mathbb{N}$) Definition. Whenever $n$ is a natural number, define that $$\langle n\rangle : \{0,\ldots,9\}^\mathbb{N}$$ is the unique ...
0
votes
1answer
34 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
0
votes
3answers
38 views

Variation on Fermat Little Theorem

Does the following variation of Fermat Little Theorem hold? How do you prove it? Let $p$ be a prime number greater than $3$. Then there exist a natural non-prime $m > 1$ such that ...
0
votes
1answer
25 views

How many $3$-digit positive integers can be represented as the sum of exactly nine different powers of $2$?

How many $3$-digit positive integers can be represented as the sum of exactly nine different powers of $2$? What does this question mean? Is the sum of $9$ different powers of $2$ like ...
2
votes
2answers
69 views

Proof of $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$

Prove that $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$ Card $\mathbb{N}^\mathbb{N} = \aleph_0^{\aleph_0}$ Card $(0, 1) = \mathbb{c}$ Define: $f: ...
0
votes
3answers
44 views

Find the value of y in $11y \equiv 14 \pmod{19}$

Find the value of $y$ in $11y \equiv 14 \pmod{19}$. My issue is not with finding a solution. Using the Euclidean algorithm and Bezout's identity I get a final expression of: $$(11)(7)(14) - ...
1
vote
1answer
25 views

Prove that if $17 \not\mid n$, then either $17 \mid n^8+1$ or $17 \mid n^8-1$

Question is : Let $n$ be a natural number not divisible by $17$. Prove that either $n^8+1$ or $n^8-1$ is divisible by $17$. I tried to solve using Fermat theorem for a prime number $p$, and any ...
0
votes
0answers
57 views

The condition that given polynomial is divisible by 3

In How can I prove that the following is divisible by 3?, I showed $k^3+3k^2+2k$ is divisible by $3$ using Euler's theorem, specifically, Fermat's little theorem. Then I thought that it is possible to ...
1
vote
3answers
46 views

If $b-a>1$ then there is a $k\in \mathbb{Z}$ such that $a<k<b$

Given $a, b \in \mathbb{R}$, such that $b-a>1$, there is at least one $k\in \mathbb{Z}$ such that $a<k<b$. My attempt: Consider $E:=(a,b)\cap \mathbb{N}$. We need to show that $E$ is not ...
1
vote
2answers
41 views

If $(d,a)=1$ and $d|ab$ then $d|b$ .

Okay, checking to see if i'm on the right track. I essentially did the same prove for Euclid's lemma but exchanged the $d$ for the $p$. Is that the right idea? Or am I missing something?
1
vote
2answers
44 views

If $\gcd(A,B,C)=1$, can we find $h$ s.t. $\gcd(A,B+hC)=1$?

If $\gcd(A,B,C)=1$, can we find $h$ s.t. $\gcd(A,B+hC)=1$? I have tried but I find I am not able to prove this. Maybe I do not know some important thing? Could someone help? Thanks!
13
votes
14answers
2k views

How to prove that $k^3+3k^2+2k$ is always divisible by $3$? [on hold]

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$? $$k^3 + 3k^2 + 2k$$
0
votes
1answer
25 views

Prove that the Gaussian integer $a$ is a prime element if $N(a)=p$ or $p^2$ where $p$ is congruent t0 3 mod 4

Let $a \in \mathbb{Z}[i]$ such that $N(a)$ is a prime or the square of a prime congruent to 3 modulo 4 in $\mathbb{Z}$. That is, $N(a)=p$ or $p^2$ where $p \equiv 3 \bmod 4$. Prove that $a$ is a ...
2
votes
2answers
27 views

Irreducible vs. reducible fractions

Let $a,b,c,d$ be positive integers. Suppose that $$\frac cd=\frac ab.$$ I want to prove that if $a$ and $b$ are relative primes, then $c/a=d/b$ is an integer. That is, the only way a fraction can be ...
0
votes
3answers
35 views

If $x$ does not equal $1$ then either $x$ is not a perfect square or $x+3$ is not a perfect square.

If $x$ does not equal $1$ then either $x$ is not a perfect square or $x+3$ is not a perfect square. I know how to prove a perfect square but no idea on this
6
votes
1answer
102 views

Is $k+p$ prime infinitely many times?

I have the following conjecture: Let $k\in\mathbb{N}$ be even. Now $k+p$ is prime for infinitely many primes $p$. I couldn't find anything on this topic, but I'm sure this has been thought of ...
0
votes
0answers
17 views

Peano's 3rd axiom -explain

Peano's axioms for Natural numbers. 3rd axiom from Introduction to topology by Bert Mendelson - There is one and only one object in $\mathbb{N}$ denoted by ...
2
votes
3answers
37 views

show $b_1b_2b_3\cdots b_{\phi(m)} \equiv 1 \pmod m$

show $b_1b_2b_3\cdots b_{\phi(m)} \equiv 1 \pmod{m}$ or $b_1b_2b_3\cdots b_{\phi(m)} \equiv -1 \pmod m$ where $b_1 < b_2 < b_3<\cdots< b_{\phi(m)}$ are the integers between $1$ and $m$ ...
1
vote
1answer
25 views

Show that if p divides ab and p divides neither a nor b, then p divides an a1b1 where a1, b1 < p.

The idea is I am trying to prove that if a prime p divides ab, p must divide either a or b. I have already proved that p cannot divide a1b1 if a1, b1 < p so now I need to show that if p divides ab ...
0
votes
1answer
17 views

The form of solutions of $p*k-q*j=r,$ for $(p,q)=1$.

I would like to find the form of solutions of $p*k-q*j=r,$ for $(p,q)=1$ for any fixed $r < pq$ and $k,j \in \mathbb{N}$. I tried to look at the divisibility of $p=cq+b.$ But I didn't have any ...
1
vote
0answers
19 views

Symmetric Coprime Pairs

I've been thinking about the distribution of the coprimes of n, and in particular, about one particular symmetry that they have. Here's a problem that I have formulated for myself: Given natural ...
-3
votes
0answers
35 views

Eulers Phi Function [on hold]

I need help with Verify that Eulers phi function gives a result of $40$ when applied to the numbers $75$. I know that $\phi(40) = 16$, $\phi (75) = 40$ Please help?
3
votes
0answers
51 views

Making $66$ with $1,1,1,1,1$

How can one make $66$ with only $1,1,1,1,1$? You cannot combine these two numbers to make a new number, such as this: $66=11 \times (1+1+1)!$. This was inspired a game of dice that I used to play, ...
1
vote
2answers
26 views

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$. I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial ...
1
vote
1answer
23 views

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) [on hold]

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) The only theorems I have learned to use in this scenario are the linear equation thm: $ax + by = gcd(a,b)$ and linear congruence thm. With ...
1
vote
1answer
41 views

Which function satisfy $f'(\mathbb{N}) \subseteq \mathbb{N}$

I was thinking and found the following question : Let $f:\mathbb{R} \to \mathbb{R}$ a differentiable function and consider the restrictions $f|_\mathbb{N}$ and $f'_\mathbb{N}$ i) Which functions ...
1
vote
1answer
35 views

Last 3 digits of Marsenne numbers

Marsenne numbers are of the form $2^{p} - 1$, $p$ is a prime. Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$. This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and ...
0
votes
0answers
10 views

Involutary Keys for Shift Cipher

Let $e_K(x)=(ax+k)\mod m$ and $d_K(x)=a^{-1}(x-k)\mod m$, where $K=(k,a)$ How can I show that $e_K(x)=d_K(x)$ if and only if $k^{-1}=k\mod m$ and $a(k+1)=0\mod m$?
6
votes
1answer
74 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $mn$ is a perfect cube. ...
0
votes
0answers
22 views

Range of inverse harmonic mean of two integers

Today I was solving an exercise and one of the things I tried (which later turned out to be useless) involved considering the following: Is there a simple way to describe in terms of $n$ the range of ...
0
votes
0answers
18 views

How to find max $c$ that solve $N \mod p^c = 0$

The title provide 100% of my question, below is explanation to why am I asking this. I been reading about the quadratic sieve article in wiki, the part where sieve is actually performed. The goal of ...
2
votes
2answers
31 views

How to find a solution knowing that gcd(512 , 200) = 8c ?

i got this for homework , but i would like to know if i'm just supposed to substitute any value i want for c and , find a solution? Or am i to use c as an arbitrary value , and find a solution which ...
4
votes
5answers
152 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
1
vote
2answers
79 views

Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any ...
0
votes
1answer
22 views

Modulus Notation Division

I have a couple of silly questions (it will definitely demonstrate my lack of ability in mathematics :P) Is there a type of reduction or absorption of modulus in congruence equations? Here's an ...
0
votes
1answer
27 views

Show that the linear Diophantine equation has infinitely positive solutions [on hold]

Any ideas on how to write down this proof? Let a and b be positive integers and assume $\gcd(a,b)|c$. Show that the linear Diophantine equation $ax-by=c$ has infinitely many positive solutions x,y.
0
votes
2answers
55 views

How to find total number of sum of consecutive number of $n$? [duplicate]

How many ways are there to write $n$ as the sum of consecutive positive integers? Example: $15$ has $3$ consecutive sums: $1+2+3+4+5=15$ $7+8=15$ $4+5+6=15$
0
votes
1answer
33 views

Divisibility criteria

Notice that by $\mod 7$ we have $$6!\equiv -1 (\mod 7)$$ $$5!1!\equiv 1 (\mod 7)$$ $$4!2!\equiv -1 (\mod 7)$$ $$3!3!\equiv 1 (\mod 7).$$ Calculate $10!, 9!1!, 8!2!, 7!3!, 6!4!, 5!5!$ by ...
5
votes
3answers
86 views

How to start this proof?

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.
0
votes
2answers
50 views

Legendre symbol, what is it?

I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression. $$\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$$
19
votes
2answers
2k views

Find a thousand natural numbers such that their sum equals their product

The question is to find a thousand natural numbers such that their sum equals their product. Here's my approach : I worked on this question for lesser cases : \begin{align*} &2 \times 2 = 2 + ...
-2
votes
1answer
45 views

Dealing with phi function property

If $n=2^kN$, where $N$ is odd, then $$\sum_{d\mid n}(-1)^{n/d}\phi(d)=\sum_{d\mid 2^{k-1}N}\phi(d)-\sum_{d\mid N}\phi(2^kd)$$ I have no idea how to seperate things inside the left side. In a ...
1
vote
2answers
57 views

Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

I am reading the wiki article about Quadratic reciprocity and I don't understand how can I tell if some integer $c$ got quadratic root mod $p$? So far I am using brute search to find $y$ such that ...
1
vote
0answers
32 views

Different representation of $f(n) = \sum_{d|n; \ \sqrt n\le d \le n}(-1)^d$

I am looking for a different way to calculate the following sum where $d,n\in \mathbb N$: $$f(n) = \sum_{d|n; \ \sqrt n\le d \le n}(-1)^d$$ Here are some example results for different values of n ...
7
votes
4answers
125 views

Find the remainder when ${{5^5}^5}^5$ is divided by $24$

Find the remainder when ${{5^5}^5}^5$ is divided by $24$ I tried using congruence modulo. $$5^2\equiv1\mod{24}$$ $$5^5=125\mod{24}$$ But this does not give the correct answer.