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

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Squares Containing digits from Fibonacci Numbers

This is a problem that I thought of myself. Currently, the digits of $F_1$ through $F_n$ are written on the chalkboard in order, where ${F_n}$ is the Fibonacci Sequence and $n \ge 5$ We shall ...
0
votes
0answers
16 views

How can I define $H+K$?

Let be integers 5 and 100, and let be $H=5Z$ and $K=100Z$ subgroups of the additive group $Z$. How can I define the subgroup $H+K$ ? I think $5Z+100Z=5Z$ because mcd(100,5)=5 but I'm not sure that ...
0
votes
1answer
17 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
1
vote
1answer
28 views

How does the fact that Fermat primes are relatively prime imply there are infinite primes?

I was just reading a book called Proofs from the Book. It presented the proof given by George Polya to prove that two Fermat primes (numbers of the form $2^{2^n} + 1$) are always relatively prime, ...
0
votes
2answers
44 views

A number theory contest problem

I have come across a problem I can't solve. Can anyone help? Here is the problem Find least integer $N$ such that sum of the digits of both $N$ and $N+1$ is divisible by $7$.
3
votes
1answer
87 views

Is it possible to find a perfect cube like 111…11?

Can we find a perfect cube like $111...111$(all digits are $1$), apart from the number $1$ itself? It's easy to prove that there can't be anything like $111...11$ that is a perfect square besides ...
2
votes
2answers
56 views

How can I prove that only there continuous odd prime are $3,5,7$?

How can I prove that the only prime number $p$, such that $ p,p+2,p+4$ are primes is 3?
1
vote
3answers
36 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
2answers
30 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 ...
2
votes
2answers
22 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
37 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
21 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
37 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
35 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
39 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
28 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
71 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
58 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
42 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
103 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
53 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
76 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 ...
0
votes
3answers
353 views

Why is the Axiom of Infinity necessary?

I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only ...
18
votes
4answers
330 views

What would Gauss do in this case: adding $1+\frac12+\frac13+\frac14+ \dots +\frac1{100}$?

We all know the story related to Gauss that Gauss' class was asked to find the sum of the numbers from $1$ to $100$ as a "busy work" problem and and he came up with $5050$ in less than a minute. He ...
0
votes
0answers
37 views

Modular Division and Factorial

I am unfamiliar with number theory but am trying to calculate the following for a coding challenge: $$\frac{(N-M-1)!}{N!(M-1)!}\pmod{Q}$$ where $Q$ is prime. I know that I can calculate the ...
64
votes
12answers
8k views

Is there something special about 2015? [closed]

Is there some property which is satisfied only by the number 2015 (among natural numbers, say) or is there a relatively simple question for which the answer is, surprisingly, 2015? This is inspired ...
13
votes
17answers
10k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
20
votes
8answers
2k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...