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

learn more… | top users | synonyms

2
votes
5answers
58 views

Prove $(a,b,c)=((a,b),(a,c))$

The notation is for the greatest common divisor. I know that $$(a,b,c)=((a,b),c)=((a,c),b)=(a,(b,c))$$ Suppose $g=(a,b,c)$. Then $g\mid a,b,c$. Also, $g\mid(a,b),c$ and $g\mid(a,c),b$. Thus ...
1
vote
2answers
33 views

Showing $p\mid(a^2 +c^2)$ given $p\mid(a^2+b^2)$ and $p\mid(b^2+c^2)$

I had no trouble showing this for $a^2-c^2$ but I'm running into a wall here. A couple of routes that I took. 1) $p\mid(a^2+b^2) \Rightarrow \exists k\in\mathbb{Z}$ s.t. $a^2+b^2 =pk$ ...
0
votes
1answer
37 views

An Inequality Involving Prime Numbers

Let $p_i$ be the $i^{th}$ prime number. It seems as though the following inequality is true for all positive integers $m$ and real numbers $x>1$: ...
0
votes
3answers
107 views

Notation for the least common multiple

Suppose I use the notation $\{a,b \}$ for the least common multiple of integers $a$ and $b$. Is this common notation in number theory (it is from Hardy and Wright), and would a mathematically literate ...
0
votes
2answers
48 views

Identity involving LCM and GCD

Let $(a,b)$ denote the GCD of $a$ and $b$, and let $[a,b]$ denote the LCM of $a$ and $b$. Prove $\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$.
5
votes
4answers
235 views

Proving an expression is composite

I am trying to prove that $ n^4 + 4^n $ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even. This problem is given in a ...
5
votes
1answer
92 views

When does $(a,b) \to (2a, b-a)$ terminate? ($a \leq b$)

I've got a following problem. Let's have two integers $a$ and $b$, assume $a \leq b$ (if not, we swap them) Algorithm is just one step, produce new numbers: $2a$ and $b-a$ Algorithm stops when $a ...
0
votes
1answer
25 views

Examples of (use of) position-systems

As you now, the most used number system is the position system with base 10, where for instance $101$ means $1\cdot 10^2+0\cdot 10^1 + 1 \cdot 10^0$. Likewise we can define binary number system with ...
1
vote
1answer
63 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
2
votes
1answer
176 views

Has this weaker version of Fermat's last theorem already had an elementary proof?

Recently I carried out an elementary proof of the following assertion, which is a special case of Fermat's last theorem: If $p$ is an odd prime and $x, y, z > 0$ are integers such that $(x, y) = ...
-1
votes
1answer
28 views

$p$ and $q$ are primes. Prove $\forall n,k\in \mathbb N, (p^n\mid q^k⇒p=q)$ [duplicate]

I'm having trouble answering this question, can anyone help explain a full solution of this problem? I will be very grateful. Thanks!
0
votes
3answers
21 views

Let n and k be positive integers. If n ≥ (k + 1), then n! + (k + 1) is a composite number

I've been having trouble with finding the proof for this question. Can anybody explain the solution to me? Thanks so much!
0
votes
2answers
48 views

Question regardles primes and the fundamental theorem of arithmetic

I have been reading through my book of practice proofs and came across this particular question which has stumped me. $p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
0
votes
2answers
37 views

Show if (m,n) = 1, then for any # p, we have (p,mn) = (p,m)(p,n).

Show that if $(m,n) = 1$, then for any number p, we have $(p,mn) = (p,m)(p,n).$
1
vote
1answer
23 views

Reduced Residue System in Mathematica

How can I create the standard reduced residue system modulo $m$ in Mathematica for a given positive integer $m$? For example, if I input $10$, I would like it to give me the list $\{1,3,7,9\}$. ...
7
votes
5answers
665 views

Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

The fundamental theorem of arithmetic is made of two parts: The existence part: There exist primes such that for any natural number $j$, we can write $j$ as a product of prime numbers. The ...
1
vote
1answer
125 views

Divisibility problem incorrect proof

here's the problem: Find all odd integers $n$ greater than $1$ such that for any relatively prime divisors $a,b$ of $n$ the number $a+b-1$ is also a divisor of $n$. And this is my proof (which I ...
1
vote
3answers
78 views

Find the remainder of $\frac{1! +2!+\, \dots\, +95! }{15}$.

I think I found my answer but I am looking for better ones
0
votes
0answers
57 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
1
vote
1answer
59 views

Proof that $a\equiv b \pmod n \iff a \pmod n = b\pmod n$

Proof that for every $a,b \in \mathbb Z,\ n \in \mathbb N$, that $$a\equiv b \pmod n \iff a \pmod n = b \pmod n.$$ My approach is: $n\mid a$ and $n\mid b$ $a\equiv b \pmod n \iff \exists x,y: ...
2
votes
0answers
35 views

Arithmetic progressions of Perfect squares [duplicate]

It is well known that the exists no arithmetic progression of squares of length 4. But I could not find a simple proof. please can you help me.
0
votes
1answer
52 views

Rearranging terms in a series

I am considering the limit of the sum S of an alternating series $p_1,n_1, p_2,n_2, p_3,n_3…$ where $p_n$ are positive and $n_n$ negative terms. If the limit exist = P of the sum of the positive terms ...
0
votes
2answers
41 views

$A^7 \not\equiv A(\mod 13) \Rightarrow A^{78} + 1 \equiv 0 (\mod 169)$

Let variable $A$ is integer and $A^7 \not\equiv A(\mod 13)$. Prove that $A^{78} + 1 \equiv 0 (\mod 169)$ Could someone explain, how to solve this type of problems? Any help would be greatly ...
4
votes
3answers
124 views

Interesting behavior of $\frac{n}{v_2(n!)+1}$.

I've lately noticed some interesting behavior from the values of the function $f(n)=\frac{n}{v_2(n!)+1}$, Where $v_p(n)$ is the $p$-adic valuation of $n$, and we also know that ...
0
votes
2answers
59 views

How to solve $ \prod \limits_{i=1}^{99}[i]_{100} $

Solve: $\prod \limits_{i=1}^{99}[i]_{100}=?$ Due to the fact that i is always smaller than 100, I assume I can solve this example just by multiplying the following values: $1*2*3*4*5…*98*99$ ? ...
0
votes
1answer
33 views

How solve $[20]_3^{-1}$?

What does this mean, $[20]_3^{-1}$? it's from the topic rings, fields and residue classes. Can you give me a hint how to solve this?
3
votes
1answer
41 views

Theorem on Giuga number

Giuga number : $n$ is a Giuga number $\iff$ For every prime factor $p$ of $n$ , $p | (\frac{n}{p}-1)$ How to prove the following theorem on Giuga numbers $n$ is a giuga number $\iff$ ...
2
votes
0answers
81 views

Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$

Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$: 2, 4, 7, 16, 29, 67, 92, 154, 191, ... It seems that all primes either is ...
1
vote
3answers
80 views

Find all values that make the expression a perfect cube [closed]

Find all the positive integers $n$ such that $n^3-n$ is a perfect cube.
3
votes
1answer
42 views

Can a Mersenne number be a power (with exponent > 1) of a prime?

Let $n \geq 1$ and consider the (Mersenne) number $M_n = 2^n-1$. Is it possible that $M_n = p^k$ for some prime $p$ and some (necessarily odd) $k > 1$? Thanks in advance.
2
votes
1answer
26 views

Divisors of at least one of three numbers

Question: Find the number of positive integers that are divisors of at least one of $10^{10}$, $15^7$, $18^{11}$. My solution (my answer was wrong): I thought that the numbers that are divisors of at ...
0
votes
1answer
35 views

Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
2
votes
1answer
74 views

LCM and GCD equation

Let $a$, $b$, $c$ be three positive integers such that $$\mathrm{lcm}(a,b)\cdot\mathrm{lcm}(b,c)\cdot\mathrm{lcm}(c,a)=a\cdot b\cdot c\cdot \gcd(a,b,c).$$ Given that none of $a$, $b$, $c$ is an ...
4
votes
2answers
93 views

Powers and differences of positive integers

Assume that $a$, $b$, $c$, and $d$ are positive integers such that $a^5=b^4$, $c^3=d^2$, and $c-a=19$. Determine $d-b$. I know this question isn't particularly hard, but I've been having trouble ...
0
votes
1answer
21 views

Position of switches based on divisibility

There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to ...
2
votes
1answer
31 views

Sum of certain integers $a$ where $a^6$ does not divide $6^a$

Find the sum of all positive integers $a=2^n3^m$ where $n$ and $m$ are non-negative integers, for which $a^6$ is not a divisor of $6^a$.
3
votes
1answer
26 views

For every positive number $n$, there exists a $n$ digit number having all odd digits and divisible by $5^n$

Prove that for every positive integer $n$, there exist a $n$ digit number, divisible by $5^n$, whose all digits are odd. for example, for $n=1, 5$ $n=2,75$ $n=3, 375$....... I have no idea how to ...
4
votes
2answers
43 views

Solving congruences

I've the following congruence system: \begin{align*} I \quad 2x \equiv 0\mod 7 \\ II \quad x \equiv 1 \mod 5\\ III \quad x \equiv 3 \mod 4 \end{align*} Now I tried to solve it: \begin{align*} II ...
5
votes
2answers
175 views

How many diamonds did they steal?

There are $7$ thieves. They steal diamonds from a diamond merchant and run away into the jungle. Whilst they're running, night falls and they decided to rest in the jungle. When everybody is ...
2
votes
0answers
29 views

Does the inverse of Euclids Pythagorean equation hold?

I know that one can generate many Pythagorean triples $(A,B,C)$, where $C^2=A^2+B^2$ with Euclid's formula: $C=X^2+Y^2$, $A=X^2-Y^2$, and $B=2 X Y$. Euclid's formula can find all primitive ...
0
votes
0answers
16 views

to maximize the summation

let F=$∑i=1$ to $N$ $((abs(A[i]-X))^P mod $K$)mod K$ $A[1..N]$ is an array with $N$ elements, the problem is to find $X$ such that the above summation F maximized where $X$ can take any value from ...
0
votes
1answer
19 views

Limits on repeated sum in circle method

In Bob Vaughan's book The Hardy-Littlewood Method, early on he gives a sum \begin{equation} \left(\sum_{m=1} ^N e(\alpha m^k)\right)^s = \sum_{m_1 = 1} ^N \sum_{m_2 = 1} ^N \cdots \sum_{m_s = 1} ^N ...
0
votes
2answers
62 views

Find all values of for which the ratio is an integer

Find all values of $n$ for which, $$\dfrac{(\dfrac{n+3}{2}) \cdots n}{(\dfrac{n-1}{2})!}$$ is an integer. I have tried the problem for some primes. Each time it seemed true. But I still ...
0
votes
1answer
40 views

Sum of divisor and positive divisor problem

The sum of all the positive divisor and the sum of their reciprocals of a number N are $195$ and $\frac{65}{24}$ respectively. Find N?
1
vote
1answer
43 views

Primes of the form $x^2+ny^2$ where $n\equiv 1\pmod{4}$ is a squarefree number

Let $n\equiv1\pmod{4}$ be a squarefree number and $p\equiv1\pmod{4n}$ be a prime number. Does there exist $x,y\in\mathbb{N}$ such that $p=x^2+ny^2$?
1
vote
1answer
37 views

Multiplicative order of n mod 2n-1

I am trying to find the smallest positive integer k such that $n^k \equiv 1 \mod(2n-1)$. Has this been solved? Any thoughts or references are greatly appreciated!
1
vote
1answer
39 views

How to calculate the number of lattice points in the interior and on the boundary of these figures with vertices as lattice points?

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers. Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
1
vote
1answer
59 views

Proof by contradiction: logarithm

I need to prove by contradiction that $\log_2(3)$ is irrational. I'm really unfamiliar with logs to be honest, it's been awhile since I've done them and I'm unsure of how to approach this. Any help ...
13
votes
2answers
211 views

Integer values of $\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$?

What are the possible integer values of $$\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$$ where $x$, $y$, and $z$ are positive integers? My suspicion is the the only integer values are $3$ and $5$, the former ...
1
vote
2answers
60 views

cannot be the value of the expression.

Which of the following can not be the value of $x/y+y/z+z/x$. Where $x$, $y$, and $z$ are positive integers? a) $4 $ b) $7/2$ c) $3$ d) $5/2$ Should I go through the options?