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

learn more… | top users | synonyms

0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
2
votes
2answers
40 views

Dividing by x on two sides of an equation is not always the same equation??

$y = p*x$ $\frac{y}{x} = \frac{p*x}{x}$ These equations are 'equal' via common math principles. If $x = 0$, then in the first equation $y = 0$. In the second equation, its not defined (since you ...
0
votes
0answers
19 views

On problem on two equations

Let $n_{1}$ and $n_{2}$ are natutal number such that $m_{11}, m_{12}\in\{0,1...,2^{n_{1}}-1\}$ and $m_{21}, m_{22}\in\{0,1...,2^{n_{2}}-1\}$. Also $m_{11}$ and $m_{22}$ are odd. Now we have equations: ...
0
votes
1answer
81 views

Without using group theory, How to Prove $n|\phi(a^n-1)$, where $\phi$ is Euler's Totient function. [closed]

Let $\phi$ be Euler's Totient funcion, how to prove this property? If possible can we have an elementary proof without leveraging the group theory? $$n|\phi(a^n-1), \forall n,a>1, \gcd(a,n)=1$$ ...
2
votes
3answers
38 views

Chinese Remainder Theorem problem error

I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively. So I start defining $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, ...
0
votes
0answers
27 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
3
votes
6answers
910 views

Among any three consecutive positive integers one is a multiple of 3

If $8q,8q+1,8q+2$ are consecutive positive integers, then prove that at least one among them is a multiple of $3$. One proof is that by expressing $8q=3m+r$. Is there any other way of doing it ...
3
votes
3answers
122 views

Divisibility of consecutive numbers by 6

Prove that the product of three consecutive positive integers is divisible by 6 by expressing the positive integer n as n=8*q+r I expressed the problem as n(n+1)(n+2) where n is a positive integer I ...
2
votes
1answer
48 views

suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
3
votes
5answers
578 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
4
votes
3answers
100 views

Elementary, direct proof of when $5$ is a quadratic residue mod $p$

$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$ It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm ...
0
votes
1answer
151 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
1
vote
1answer
48 views

Solving Equations in $\mathbf{Z}/n\mathbf{Z}$ with Indices

Consider the equation $x^4 = 7,$ which we wish to solve in $\mathbf{Z}/29\mathbf{Z}.$ I was taught a technique for solving this problem, but I can't understand it. I'll try my best to describe it, ...
2
votes
2answers
54 views

Geometrical proof of the existence of square roots

This is quite an easy question, but it's been troubling me and I can't manage to work it out. I've been reading the book A Concise Introduction to Pure Mathematics (M. Liebeck), so I'll quote the ...
7
votes
0answers
59 views

Find all integer solutions of the equation

Find all integer solutions to $3^a+7=2\cdot5^b$. Basically I've tried almost every tool I know of NT (Zsigmondy,LTE,reducing to various modulus) but nothing worked. So far I just know that (1,1) ...
0
votes
2answers
76 views

Which prime $p$ makes $\frac{7^{p-1}-1}{p}$ and $\frac{11^{p-1}-1}{p}$ be perfect squares? (not simultaneously)

Let $p$ be a prime number. Then which $p$ makes $$\frac{7^{p-1}-1}{p}$$ be a perfect square? Similarly, which $p$ makes $$\frac{11^{p-1}-1}{p}$$ be a perfect square?
5
votes
4answers
72 views

Proof of $ x (x+1) $ is an even number by contradiction proof method

Prove that $ x(x+1) $ is always even by the method of contradiction. I assumed $ x(x+1) = 2k + 1 $ as an odd integer where $ k $ is an integer Add $1$ to both sides, we get $ x (x+1) + 1 = 2k + 1 + ...
0
votes
0answers
92 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
0
votes
2answers
35 views

Determine the congruence class of $\ 5^{-3} \in \mathbb{Z}/7\mathbb{Z}$.

I have this question in my homework and I don't quite understand the notation. Determine the congruence class of: $$\bar5^{-3} \in \mathbb{Z}/7\mathbb{Z}$$ Any tips or hints on what's being asked or ...
1
vote
2answers
68 views

Prove that if $n \geq 2$, then $\sqrt[n]{n}$ is irrational. Hint, show that if $n \geq 2$, then $2^{n} > n$.

Prove that if $n \geq 2$, then $\sqrt[n]{n}$ is irrational. Hint, show that if $n \geq 2$, then $2^{n} > n$. So, my thought process was that I could show that $2^{n} > n$ using induction, but ...
0
votes
1answer
144 views

If $x \ge 5 \in \mathbb Z$, then $x$ has a square mate $y$ with $y < x$.

A pair of positive integers are called square mates if their sum $x + y$ is a perfect square.(The concept of square mates is contrived just for this problem.) There's a positive square integer ...
0
votes
1answer
40 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
2
votes
1answer
48 views

Let $N$ and $M$ be two digit numbers. Then the digits of $M^2$ are those of $N^2$, but reversed.

Let $N$ be a two digit number and let $M$ be the number formed from $M$ by reversing $N$'s digits. The digits of $M^2$ are precisely those of $N^2$, but reversed. $Proof$: Since $N$ is a two ...
1
vote
3answers
64 views

How does $n+2\mid(n^2+n+1)(n^2+n+2)$ imply $n+2\mid12$? [closed]

I'm trying to show that if $n+2\mid(n^2+n+1)(n^2+n+2)$, then $n+2 \mid 12$ for all $n\in \mathbb{N}$.
1
vote
1answer
27 views

Estimate or calculate the number of digits of a multiplication

I would like to calculate the number of digits of these multiplications 2 x 4 200 x 300 2 (12321) (1000). I don't exactly know how to start. Of course I know that I can multiply the numbers and ...
2
votes
4answers
178 views

Number of numbers between a and b and sums from x to y

This is for my benefit and curiosity and not homework. How do you calculate the number of numbers between $1$ and $100$? How do you calculate the number of even and odd numbers between $1$ and $100$? ...
1
vote
1answer
16 views

Solutions with powered modulus $m^s$

Suppose $(a,m)=1$, where $(,)$ denotes the gcd, and let $x_1$ denote a solution of $ax\equiv 1\pmod{m}$. For $s=1,2,...$ let $x_s=\frac{1}{a}-\frac{1}{a}(1-ax_1)^s$. Prove that $x_s$ is an integer ...
7
votes
0answers
118 views

Show that $x$ is rational.

Sincerely, I don't have the slightest idea for this one : Suppose that $a,b$ are distinct positive integers and that the numbers $\lfloor a^n x\rfloor $ with $n\in\Bbb{N}$ and $x$ a fixed real ...
0
votes
2answers
33 views

calculate reverse number with 2 conditions

I can't find the reversed number of $2 \mod 13$ ($2^{-1}=?$) that is also a solution to $$5x = 2 \mod 13.$$ How can I find it? Thanks!
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
118 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
201 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
39 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
2answers
54 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
1
vote
5answers
86 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
29 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
79 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
129 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
62 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
96 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
163 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!