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

learn more… | top users | synonyms

0
votes
1answer
20 views

On the number of digits for irrational numerical base systems

I am trying to grasp an idea on irrational numerical base systems - namely base $\pi$, $e$ etc. As I understand it from some articles, for a given base $b$ (integer or not) one would only need $[b] - ...
5
votes
2answers
116 views

How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

The Wikipedia article for the Collatz conjecture states that: The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$. It gives ...
1
vote
3answers
90 views

Solving $a^2+3b^2=c^2$

I'm looking for how to solve the equation $a^2+3b^2=c^2$ where $a,b,c$ are integers and $b$ is even, I'm looking for the algorithm used to solve this kind of equations, not just the solution. Regards ...
0
votes
1answer
36 views

Find a polynomial with certain conditions.

Suppose that: $$f(x) = 3\frac{x^4+x^3+x^2+1}{x^2+x-2}.$$ Find a polynomial $h(x)$ such that $f(x) + h(x)$ has horizontal asymptote of 0 as $x$ approaches positive infinity.
4
votes
2answers
38 views

Non-negative fractions summing to $1$

Let $ d_1,\ldots, d_n \ge 2 $ be pairwise relatively prime. Are there any $ c_1,\ldots,c_n \in \mathbb{Z}_{\ge 0} $ with $ c_i \le d_i-1 $ for all $ i=1,\ldots,n $, such that $\displaystyle ...
1
vote
3answers
62 views

$3$ doesn't divide $x\Longrightarrow\;x^3\equiv\pm1 (\operatorname{mod}9)$ [closed]

I'm stuck in this elementary problem: how can I show that $3$ doesn't divide $x$ implies $\;x^3\equiv\pm1 (\operatorname{mod}9)\:$? Thanks a lot
-1
votes
2answers
198 views

Count the whistles

Sports Teacher gathered all the players in his garden and ordered them to line up. After the whistle all players should change the order in which they stand. Teacher gave all the students numbers ...
0
votes
1answer
38 views

a finite induction question from burton's elementary number theory

this question comes from burton's elementary number theory, 4th edition. question 3 in 1.1 says to use the second principle of finite induction to establish that $$for\ all\ n\ge1,\ ^{(a)}\ ...
10
votes
0answers
95 views

Peculiar numbers

This is from the weekly math challenge of the French newspaper Le Monde. "Magical" numbers have a remarkable property: when one of them, say $n$, is squared, it is such that $n^2$ ends with $n$. ...
1
vote
1answer
56 views

Alternative proof for elementary number theory lemma

Let $a, b \in \mathbb{N}, (a,b) =1$.Then for any $c \in \mathbb{N}, c \ne a, b$, there is an $m \in \mathbb{N}$ s.t. $$(c, a + bm) = 1$$ I can solve this using general principles, but found it as an ...
1
vote
5answers
85 views

Distribution of integer solution pairs (x,y) for $2x^2 = y^2 + y$

I am looking for integer pairs $(x,y)$ that respect $$2x^2 = y^2 + y$$ For example $(6,8)$ is a solution for that. Simple solution is to enumerate on $x$ or $y$ and test if the corresponding ...
1
vote
1answer
28 views

Dirichlet convolution for dummies

Can someone explain me meaning and usefulness of Dirichlet convolution? I know the concepts of summation function over divisors of number and its Moebius inversion. But how does it relate to Dirichlet ...
1
vote
6answers
50 views

Prove that $\gcd(n,p-1)=1$ if $p$ is the smallest prime divisor of $n$

Let $n$ be a natural number greater than $1$, and $p$ be the smallest prime divisor of $n$. How can I prove that $\gcd(n,p-1)=1$?
0
votes
2answers
78 views

Simple math pattern--does it work?

So a friend of mine just pointed this out: $$ \text {If} \ \; 0<a<b \; \text{then} $$ $$ b^3-a^3=(a^2+ab+b^2)(b-a) $$ $$ b^4-a^4=((a^3)+(a^2b)+(ab^2)+(b^3))(b-a) $$ $$ ...
5
votes
0answers
128 views

$(b-a)^2-2ab$ is a perfect square.

I'm in need of some help if possible, about a formula, theorems, old works, ideas, or even an existing solution are welcome. The problem is that i have two distinct natural numbers as $b > a > ...
5
votes
1answer
61 views

How many decimal representations are possible for the number 1

I know that there at least two $0.\overline{9}$ and 1 Is there a neat and more concrete way to understand this problem.
2
votes
2answers
67 views

Divisor Pattern - Number Theory

List all positive divisors of $18 $ List all positive divisors of $75 $ Find another number with the same number of divisors. What is the pattern? $18 – 1,2,3,6,9,18 $ $75 – 1,3,5,25,75 $ $99 – ...
7
votes
1answer
95 views

Product of factorials divided by factorial to produce perfect square

Let $ S = 1! ~2!~\dotsm ~100! $. Prove that there exists a unique positive integer $k$ such that $S/k!$ is a perfect square. I thought this was a cute, fun problem and I did solve it, but any ...
1
vote
1answer
67 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
4
votes
6answers
162 views

Prove that in each year, the 13th day of some month occurs on a Friday [duplicate]

Prove that in each year, the 13th day of some month occurs on a Friday. No clue... please help!
2
votes
1answer
73 views

Infinite families of prime numbers

What interesting/useful infinite families of prime numbers are there? Right now it would be useful if I could find one with arbitrarily many 1's in its binary representation, but I am doing a larger ...
3
votes
1answer
41 views

Number theory notation

I am confused with the below notations . I know that ($a \equiv b \mod {n} )\iff ( n|(a-b)$ ) but what the below notation says ? $a = b \mod {n}$ and in theorem 16 in this ,it's given as below ...
1
vote
1answer
35 views

Showing $(m,n)=(u,v)$ given initial conditions

I am working on my proofs, and I think this is valid. Can anyone confirm? For the initial conditions, we have that there are integers $a,b,c,d,m,n,u,v$ such that $$ad-bc=\pm1, u=am+bn, v=cm+dn$$ ...
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
38 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
108 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
64 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 ...
4
votes
0answers
194 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
38 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
24 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$ ...