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

learn more… | top users | synonyms (1)

4
votes
1answer
93 views

How many integers between $1$ and $2016$ are divisible by a nontrivial cube $p^3$, $p > 1$? [closed]

How many integers between $1$ and $2016$ are divisible by a nontrivial cube $p^3$, $p > 1$?
0
votes
1answer
29 views

Calculate the sum under gcd

I have a question: How can I calculate $$\sum_{i=1\atop \gcd(i,75)=1}^{75} i=?$$
5
votes
3answers
133 views

Is $x^2+x+1$ divisible by $101$, if $x\in\mathbb Z$?

Prove $x^2+x+1$ isn't divisible by $101$, for any $x\in\mathbb Z$? I think the way of solving the problem it by using "Fermat's Little Theorem".
8
votes
3answers
252 views

Finding the solution of a congruence.

Solve the congruence $$4x\equiv16\mod{26}.$$ How do I find the solution to this? I have tried by the euclidean algorithm but the gcd is not $1$ so it doesn't work. $$\begin{align} ...
0
votes
1answer
64 views

Product of two distinct odd primes is not carmichael

Let $p,q$ be distinct odd primes. Define $N=pq$. Then $N$ is not a carmichael number. Proof: Suppose $N$ is carmichael. By the Chinese remainder theorem we can find a primitive root ...
2
votes
0answers
51 views

The smallest number that can be written as the sum of two or more consecutive integers in exactly 1000 ways

What is the smallest number that can be written as the sum of two or more consecutive integers in exactly 1000 ways? I was reading this question from Link . I have understood the theory behind it. ...
0
votes
1answer
35 views

Exercise 3 on page 5 and exercise 7 on page 6 in Koblitz's Introduction to modular forms.

I want to prove $1$ cannot be a congruent number, by using the fact that if it were congruent then the equation $x^4-y^4=u^2$ would have a solution in integers with $u$ being odd. I proved this last ...
5
votes
3answers
100 views

Solutions to $x+y+z-2 = (x-y)(y-z)(z-x)$

Show that the equation $$x+y+z-2 = (x-y)(y-z)(z-x)$$ has infinite solutions $(x,y,z)$ with $x, y,z$ distinct integers. In my attempt to solve the problem only found solutions form $x=y, z=2-2x$. ...
3
votes
5answers
110 views

Prove $a/b+b/a$ for $a$ and $b$ natural is only natural for $a=b$ [closed]

Is it possible to prove that for any natural $a,b$ the value of $a/b+b/a$ will not be natural with exception $a=b$?
1
vote
1answer
25 views

Quadratic function that produces natural number from natural number inputs

I am currently trying to find a way to generate different (preferably quadratic) function as part of a encryption algorithm such that : ...
7
votes
2answers
634 views

Prove that greatest common divisor of two numbers multiplied with itself divides the product of those numbers

$a, b, c \in \mathbb{N} $ if $c$ is the greatest common divisor of $a$ and $b$, $c^2$ divides $a\cdot b$. $c = \gcd(a, b) \implies c^2|ab $ How would I prove this? I understand why this sentence is ...
2
votes
3answers
46 views

Induction Proof for $fib_{2n} = (fib_{n+1})^{2} - (fib_{n-1})^{2}$

As stated in the tag, I'm trying to prove by induction the claim $f_{2n} = (f_{n+1})^{2} - (f_{n-1})^{2}$, where $f_{n}$ is the $n^{th}$ Fibonacci number. I've spent hours on the inductive step ...
1
vote
1answer
22 views

Shortest way of finding the number of incongruent roots modulo 13 of $x^2+1$

Find the number of incongruent roots modulo $13$ of $x^2+1$. I tried using complete residue system. But I want use a method that is less tedious than CRS. Any help will be appreciated!
1
vote
1answer
32 views

How to find complete set of incongruent primitive roots mod 17

How to find complete set of incongruent primitive roots $\mod{17}$? I tried to find the how many of these primitive root are there for $\mod{17}$ by using this $\phi(\phi(17))$ = $\phi(16)$ = ...
0
votes
0answers
7 views

Rate of change of a variable: adding cross products

Say there is a variable, Nominal GDP growth, and it's a function of 1) growth of inflation and 2) growth of quantity of goods and services produced in the economy (i.e. growth of real GDP). The rate ...
1
vote
2answers
38 views

Circle inscribed in Pythagorean triangle

Given the question (from Burton): "For an arbitrary positive integer $n$, show that there exists a Pythagorean triangle the radius of whose inscribed circle is $n$." My solution is $3n$,$4n$,$5n$ ...
3
votes
1answer
30 views

Cardinality of largest set $S$ such that no two numbers in $S$ have a sum divisibly by $5$.

What is the largest subset of numbers from $1$ to $100$ such that no two numbers in the chosen subset will have a sum divisible by 5. I started by considering the largest subset of numbers from ...
0
votes
0answers
26 views

Let $n\in \mathbb{N}$ and $p>2$ a prime number show that $(1+p)^{p^n} \equiv 1+p^{n+1} \ [p^{n+2}]$

I tried an induction on $n$ : For $n=0$, we obtain : $1+p \equiv 1+p \ [p^2]$ it is right ! For $n=1$, I get : $(1+p)^p = \sum \limits_{k=0}^p \binom pk p^k$ and I noticed that for $k\in ...
0
votes
1answer
42 views

How to find the missing digit?

A student calculated the value of $1 \times 2\times 3\times \cdots \times 2015\times 2016=2016!$ Then he took the summation of all digits of that answer ! He got $24135$ , but later he realized ...
5
votes
1answer
54 views

Proving minimum number of chairs is $567$

Hints only please! I am trying to figure this out somehow. A row can have as many girls, and a column can have as many boys. Proof by contradiction seems like a good technique, but I am not sure ...
1
vote
1answer
22 views

Clock angle and time passed with minute and hour hand

Let the angle the minute hand covered be $x$ [in degrees] Let the angle the hour hand covered be $y$ [in degrees] I believe that $y = 360 - x$ because of how it is shaped. Hours passed ...
5
votes
6answers
577 views

New largest prime number discovery - what's all the fuss [duplicate]

So I've read about the latest largest prime number discovery (M74207281), but I find it hand to understand what's the big deal because using Euclid's proof of the infinitude of primes we can generate ...
-2
votes
3answers
19 views

Collecting sufficient conditions for Sorli's conjecture on odd perfect numbers

(Note: This question has been cross-posted from MO.) Sorli's conjecture predicts that, for an odd perfect number $N$ given in the Eulerian form $N = {q^k}{n^2}$ (where $q$ is prime with $\gcd(q, n) ...
0
votes
0answers
26 views

Reciprocals of integers form an arithmetic progression

Prove that there exists a constant $c>1$ such that for any $n\geq 2$ and any sequence $a_0<a_1<\cdots<a_n$ of positive integers with $1/a_0,1/a_1,\ldots,1/a_n$ forming an arithmetic ...
0
votes
0answers
44 views

Solving for 2 unknowns in a perfect square

Basically was looking at a sequence of perfect squares for a given constant integer A, where in the first instant we can easily and trivially generate a sequence of perfect squares using the ...
0
votes
0answers
41 views

Prime Power Divisibility and Wolstenholme Theorem

In A. Gardiner's paper: Four Problems on Prime Power Divisibility, Amer. Math. Monthly 95(1988),926-931, He said that ``A simple calculation then shows that (for $p\geq5$)'' ...
0
votes
2answers
38 views

Integral Solutions in Diophantine Equation

How do you solve this problem: Describe the integral solutions to the equation $317a + 241b = 9.$ I know the answer is $(a, b) = (35 + 241k, −46 − 317k)$ for integers k but I don't know how ...
1
vote
0answers
42 views

Generate All Triangular Square Numbers Recursively?

We define a triangular number as follows: $$\sum_{n=1}^{n} x_{i}$$ As in $T_3$ = $3+2+1$, or $6$. Generating these triangular numbers is rather simple and done by the equation: $$T_n ={(n^2 + ...
0
votes
1answer
31 views

How to find $n$ if $a^n \equiv r \pmod m$

In particular I'm looking at the problem: \begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*} And I want to find $n_1, ...
2
votes
3answers
150 views

Prove that $3^x + 3^{x-2}$ ends with $0$ for any integer $x > 1$

I think that $3^x+3^{x-2}$ ends in a $0$ (i.e. is divisible by $10$) $\forall x \in \Bbb Z, x > 1$. Examples: $3^2+3^{2-2}=9+1=10 \\ 3^3+3^{3-2}=27+3=30 \\ 3^4+3^{4-2}=81+9=90 .$ In fact, I ...
0
votes
0answers
22 views

Confusional step about proof of divisibility by $7$.

I am reading the proof of the divisibility rule of $7$ here (Aops page),but I can't see how $k-2n_0 \equiv 2n_0 +6k $ is derived. I've tried to derive it by this $$2n_0 +6k \equiv 2n_o +7k-k ...
0
votes
1answer
26 views

How to prove or disprove that if $x \equiv c \mod n $ then $ x \equiv -c \mod n $

I am studying modular arithmetic and I don't know how to prove or disprove the following : If $x \equiv c \mod n $ then $x \equiv -c \mod n$ By trying different numbers it seems as this is true ...
-1
votes
1answer
62 views

5-digit square has sum not 29. [closed]

Show that there is no five-digit number is a square number . where the sum of his digit is 29 , I tried to solve this question more and more , But , I didn't get any solution . I hope I can ...
4
votes
1answer
24 views

Are my proofs of the basic order properties of $\mathbb{N}$ correct?

In Terry Tao's Analysis I, the basic properties of order of $\mathbb{N}$ are given, and the proofs are left as an exercise. I have worked through them, but I need someone to check if I'm not deluding ...
1
vote
1answer
38 views

Prove if $\gcd(a,7) = 1$ then $a^3 - 1$ or $a^3 + 1$ is divisible by 7

I am trying to prove if $$\gcd(a,7) = 1$$ then $$a^3 - 1$$ or $$a^3 + 1$$ is divisible by 7. (Using Little Fermat Theorem.) Obviously, $a^6 = 1 (\bmod 7)$, but how do I use that in this instance?
1
vote
2answers
52 views

For any integer $n$ greater than $1$,how many prime numbers are there greater than $n!+1$ and less than $n!+n$?

For any integer $n$ greater than $1$,how many prime numbers are there greater than $n!+1$ and less than $n!+n$ ? By trying different values of $n$ for $n=2,3,4,5,6$ I get a feeling that the number of ...
3
votes
2answers
63 views

Prove: If $\gcd(a,b)=1$, then $\gcd(2a,2b)=2$.

What I came up with is: Let $\gcd(a,b)=1$, then $1|a$ and $1|b$. There exists a, $d$ and $c$ such that $d(1)=a$ and $c(1)=b$. Then, $(2)d=(2)a$ and $(2)c=(2)b$. Thus, $2|2a$ and $2|2b$. So, ...
10
votes
3answers
165 views

Prove that $\frac{2^{122}+1}{5}$ is a composite number

As in the title. It's very easy to show that $5|2^{122}+1$, but what should I do next to show that $\frac{2^{122}+1}{5}$ is a composite number? I'm looking for hints.
1
vote
3answers
64 views

What is the largest integer which must evenly divide all integers of the form $n^5-n$?

What is the largest integer which must evenly divide all integers of the form $n^5-n$ ? I am stuck on this problem,I don't know how to approach this. Some scribble I've tried is: Given that $n^5-n ...
0
votes
3answers
90 views

Proof that $(3\cdot 2^n-1)$ is not a multiple of $17$ for any value of $n$ [closed]

Prove that $3\cdot 2^n-1$ is not a multiple of $17$ for any positive integer $n$.
0
votes
3answers
48 views

Find the sum of all $x$, $1 \le x \le 100$, such that $7$ divides $x^2+15x+1$.

Find the sum of all $x$, $1 \le x \le 100$, such that $7$ divides $x^2+15x+1$. I am clueless about how to approach this problem. Trying some values of $x$ I've found $2,4,9,11,16$ to satisfy ...
0
votes
0answers
44 views

Finding cardinality of a set which sum of its elements equal to an integer

Let $A_m$ be a set such that $$ A_m = \left\{(a_1,a_2,\ldots, a_n)\in \mathbb{N}^n |\, a_1 + a_2 + \ldots + a_n = m \right\} $$ Can we calculate cardinality of $A_m$, i.e Card(A_m) = |A_m| = ? Thank ...
0
votes
0answers
40 views

Show that the integers $a$ and $b$ can be chosen such that $ ha-kb=1$ holds for any given integers $h$ and $k$

During a longer calculation I encountered a problem where I need to show that one can pick two integers $a$ and $b$ such that $ha-kb=1$. Here $h$ and $k$ are two given integers. We have to assume ...
1
vote
1answer
24 views

Sequence of remainders of multiples

I am interested in the sequence of remainders of the integers $kp$ when divided by $q$, with $\gcd(p,q)=1$. For instance, with $p=7,q=17$, ...
5
votes
2answers
141 views

If $a^4 + 4^b$ is prime, then $a$ is odd and $b$ is even.

We say an integer $p>1$ is prime when its only positive divisors are $1$ and $p$. Let $a$ and $b$ be natural number not both $1$. Prove that if $a^4+4^b$ is prime, then $a$ is odd and $b$ is even. ...
-2
votes
2answers
79 views

Is $0$ stands for “nothing” or “none” [closed]

If the answer is yes how one can say $-1 < 0$, i.e how "something" can be smaller than "nothing"? If the answer is no, how $0$ is defined in mathematics?
0
votes
2answers
49 views

Congruence for large modulus

The idea it to find remainder $35^{32} + 51^{24} \bmod 1785$. 1785 is a composite number equal to 3 x 5 x 7 x 17. 35 is 0 mod 5 and mod 7. 51 is 0 mod 3 and mod 17. Any help regarding steps from ...
1
vote
1answer
58 views

Elementary proof of the prime number theorem?

The prime number theorem is equivalent to $\lim_{x \to \infty} \dfrac{1}{x} \left| \sum_{n\leq x} \mu(n) \right| = 0$, where $\mu(n)$ is the Mobius function. We know that $\left| \sum_{n\leq x} ...
2
votes
4answers
80 views

Why does division by zero not have an imaginary number “option”? [duplicate]

In regular math, you cannot get the square root of a negative number. Likewise, you cannot divide by zero. Both dividing by zero and taking the square of a negative have no place in real life. ...
3
votes
1answer
35 views

Diophantine equation with $gcd = 1$

John has $100$ marbles and wants to split them into $4$ groups $A,B,C,$ and $D$ such that the greatest common divisor of the number of marbles in all of the groups is $1$. Find the number of ways ...