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

learn more… | top users | synonyms (1)

1
vote
3answers
34 views

Modulus operation finding value sattisfying given condition

Find the minimum value of $p$ such that $5^p \equiv 1 \pmod p$. What is the approach to solve such questions?
4
votes
2answers
45 views

How do you solve $x^2 - 4 \equiv 0 \mod 21$

There is an example in my textbook of how you solve: $$ x^2 -4\equiv 0 \mod 21 \Leftrightarrow x^2-4\equiv 0 \mod 3 \times 7$$ and then 2 congruences can be formed out of this equation if: ...
0
votes
1answer
37 views

Does $x^2+1$ have roots in $Z_{103}[x]$?

I am trying to figure out if $x^2+1$ has any roots in $Z_{103}[x]$, but I don't have any idea of how I should find the answer. Any help would be much appreciated. Thank you.
1
vote
3answers
36 views

Divisors of $25^2+98^2$

How many divisors does $25^2+98^2$ have? My Attempt: Calculator is not allowed but using calculator I found $193\times53$ that means $8$ divisors and that $4$ of them are positive.
1
vote
1answer
25 views

Sum of powers congruence

Consider the sum $$S_n = \sum_{i=1}^n i^n,$$ and the sum mod $n$ $$M_n = S_N \text{ mod } n.$$ It is simple to prove that if $n$ is an odd prime then $M_n = 0$: if $n$ is prime then the map $x ...
0
votes
0answers
22 views

The best notation for this identity involving pentagonal numbers $\omega(n)$ and the $3x+1$ map

Let the $3x+1$ map $$ f(x) = \begin{cases} 3n+1 & \text {if $n$ is odd} \\ \frac{n}{2} & \text {if $n$ is even} \end{cases} .$$ Now we read the Wikipedia's page for the Collatz ...
0
votes
0answers
26 views

Co-finite difference sets of rationals and real numbers [on hold]

Let $G$ be an infinite abelian group, $A\subseteq G$ and put $A-A=\{a_1-a_2: a_1,a_2\in A\}$. It is clear that if $A-A=G$ then $A$ is a generating set of $G$. Now, we are interested in those subsets ...
-1
votes
0answers
17 views

On Markov triples and the square root of $2\times 2$ matrices

Let for two Markov triples $a^2+b^2+c^2=3abc,$ and $\alpha^2+\beta^2+c^2=3\alpha\beta c$, where we (can) take $a\leq b\leq c$ and $\alpha\leq \beta\leq c$. Then one has the ratio between RHS's and ...
1
vote
1answer
28 views

Find two natural numbers $m$ and $n$ such that the order of $n$ modulu $m$ equal to $2012$

Find two natural numbers $m$ and $n$ such that $\gamma_m(n)=2012$ My atempt: $$\varphi(n)\mid2012$$ $$\Longrightarrow \varphi(n)\in\{1,2,4,503,1006,2012\}$$ I am stuck here
-3
votes
0answers
24 views

Meaning of notations [on hold]

What do these six symbols mean or how do we use them?
1
vote
1answer
90 views

Why is this fact about the totient function true? [duplicate]

$$ \sum_{k<n} {gcd(k,n)=1}k = \frac{1}{2} n \phi(n)$$ This is a homework problem. I would ideally like to get to the final proof on my own. But at the moment I can't even decide how to begin. The ...
1
vote
0answers
14 views

Proof of a Stronger Version of Dirichlet's Approximation Theorem

If $\alpha$ is a real number and $n$ is a positive integer, there are integers $a$ and $b$ such that $1\leq a \leq n$ and $|\alpha a - b| < \frac{1}{n+1}$. Here is an attempt of the proof. I'm ...
7
votes
1answer
75 views

A very difficult Diophantine problem $n^2 \mid 3^n+2^n+1$

Prove that $n=3$ is the only positive integer greater than $1$, for which$$n^2 \mid 3^n+2^n+1$$This is a conjecture.
4
votes
1answer
46 views

Prove that if $p \mid a-b$ then $p^{n+1} \mid a^{p^n}-b^{p^n}$

I need help with the following problem, I don't know how to continue. Let $p$ be a prime. Prove that if $p \mid a-b$ then: $$p^{n+1} \mid a^{p^n}-b^{p^n}$$ At first I thougt the following: $$p \mid ...
3
votes
2answers
35 views

The order of $33\pmod{83}$

Find $\gamma_{83}(33)$ My attempt: stupid approach: $33^1\equiv 33 \pmod{83}$ $33^2\equiv 10 \pmod{83}$ $33^3\equiv 81 \pmod{83}$ $33^4\equiv 17 \pmod{83}$ $33^5\equiv 63 \pmod{83}$ ...
2
votes
3answers
390 views

Least Common Multiple of Fractions

how do i find lcm of two fractions? For example: $\frac{2}{3}$ and $\frac{5}{8}$
1
vote
2answers
48 views

Prove that the diophantine equation $x^2 + (x+1)^2 = y^2$ has infinitely many solutions in positive integers.

Prove that the diophantine equation $x^2 + (x+1)^2 = y^2$ has infinitely many solutions in positive integers. Now, that's a Pythagorean Triplet. So, we have to prove that there are infinitely ...
1
vote
2answers
10 views

the connection between $\gamma_m(a)$ and $\gamma_m(b)$ when $a\cdot b\equiv 1\pmod m$

show the connection between the order of $a$ $\gamma_m(a)$ and the order of $b$ $\gamma_m(b)$ when $$a\cdot b\equiv 1\pmod m$$ I took $a=5$ and $b=4$ $$5\cdot 4\equiv 1\pmod{19}$$ ...
1
vote
3answers
54 views

Find two fractions such that their sum added to their product equals $1$

This is a very interesting word problem that I came across in an old textbook of mine. So I managed to make a formula redefining the question, but other than that, the textbook gave no hints really ...
9
votes
4answers
186 views

Determine $4$ specific digits in $34!$

Find the values of $a,b,c,d\in\mathbb{N}$ such that $$ 34!=295232799cd9604140847618609643ab0000000 $$ My Attempt: The factorial of $34$ contains a $3$, so the RHS must be divisible by $3$. ...
0
votes
0answers
9 views

Need help in understanding a solution regarding divisibility

I found this question in the mathematical circles textbook which asked if a number with a hundred 0's , hundred 1's and hundred 2's be a perfect square. As of a solution they pointed out that the ...
1
vote
3answers
53 views

Solve $636^{369}\equiv x\pmod{126}$

Solve $$636^{369}\equiv x\pmod{126}$$ My attempt: $$126=2\times 3^2 \times 7$$ $$\varphi(126)=\varphi(2)\times \varphi(3^2)\times \varphi(7)=36$$ $$\color{gray}{636=6\pmod{126}}$$ ...
4
votes
3answers
86 views

Find the missing digits in the expansion of $34!$ [on hold]

If $34!=295232799cd96041408476186096435ab000000$ then find the value of $a,b,c$ and $d.$ My Attempt: I can find that $b=0$ because it has seven five integers. Note: calculator is not allowed.
14
votes
12answers
21k views

Proof that $n^3+2n$ is divisible by $3$

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs! Problem: For any natural number $n , n^3 + 2n$ is divisible by $3.$ This makes sense ...
3
votes
0answers
72 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
6
votes
3answers
78 views

Factor proofs problem

The coolness of an integer is equal to the integer divided by the total number of factors that it has. For example, $48$ has $10$ factors therefore, coolness $(48) = \frac { 48 }{ 10 } =\quad 4.8$ ...
6
votes
1answer
42 views

Infinitely many pairwise congruent solutions modulo $c$?

The following is from my number theory textbook.. In particular, there exists an integer $c$ such that there are infinitely many solutions to the equation $x^2 - dy^2 = c$. Since there are only a ...
0
votes
3answers
103 views
0
votes
1answer
64 views

How do I make this formula for the primes more concise?

The form I made for the $(n+1)^{th}$ prime $p_{n+1}$ is $\displaystyle1+\sum_{j=1}^{2p_n-1}\lfloor\frac{p_n!^j}{j!}\rfloor-\lfloor\frac{p_n!^j-1}{j!}\rfloor=p_{n+1}.$ Problem is, just like any ...
2
votes
1answer
64 views

Is this polynomial time for greatest prime factor of odd numbers?

For natural numbers $n$ and $x,$ the number of $n^{th}$ roots that have $x$ in the whole numbers place can be represented as $(x+1)^{n}-x^{n}.$ For $p$ prime, $(x+1)^{n}-x^{n}-1\equiv0\bmod p$ iff ...
5
votes
5answers
2k views

A “number” with an infinite number of digits is a natural number?

The set of natural numbers is infinite and countable. Ok. But think of an object with infinite digits (141258173412873....). Is it a natural number? Edit: What i found confusing was the fact that, ...
1
vote
1answer
19 views

Find Natural Numbers such that: $x^{(1)}y^{(1)} > x^{(2)} y^{(2)} \geq (x^{(1)} + 1)(y^{(1)} - 1)$

Consider two natural numbers $x^{(1)} \in \mathbb{N}$ and $y^{(1)} \in \mathbb{N}$ with the following relation: $x^{(1)}y^{(1)} > (x^{(1)} + 1)(y^{(1)} - 1)$. I am wondering if exists a different ...
2
votes
3answers
59 views

Determining parity of a number

I have this function: $$f(n) = \frac{(-1)^n + 1}{2}$$ For $n \in Z$ It seems be equal to $1$ if $n$ is an even number and $0$ otherwise: $$ \begin{array}{c|c} n & -3 & -2 & -1 & 0 ...
-1
votes
4answers
43 views

reasoning based question [on hold]

If 100 apples are to be divided among 25 people,how they can be divided so that none of them gets an even number of apples?
1
vote
2answers
70 views

How to find remainder of a very large number when divisor is 17?

How to find the remainder when $2^{2015}$ is divided by $17$? I tried dividing $2,4,8,16$ etc by $17$ and finding the remainder in each case to form some particular sequence but failed can someone ...
5
votes
4answers
303 views

How to factor 5671?

The other day I wanted to factor 5671 in my head. (It turns out to be $53\cdot107$, but I did not know this at the time.) I quickly ruled out the easy divisors, 2, 3, 5, 7, 11, and 13. At this point ...
0
votes
3answers
29 views

Decomposition of periodic functions

Suppose that $f$ is a periodic function defined on the integers with period $mn$, with $m$ and $n$ coprime integers. Does there necessarily exist a function $g$ with period $m$ such that $f-g$ is ...
4
votes
3answers
737 views

Product of two negative numbers is positive [duplicate]

What is the practical proof for $-1(-1)=+1$. Actually multiplication is repetitive addition. I am struggling how can I provide an activity to prove practically $-1(-1)=+1$
0
votes
0answers
109 views

What field of maths is this?

Suppose I have a simple function $f(n,x)$ which for some integer $x$ generates a unique rational number $f$ for each $n\in\mathbb{N}$ - for argument's sake lets imagine it's $\frac{x^2}{5n}$. Suppose ...
-1
votes
0answers
86 views

IONOFs Problem Solving

This was a practice question given to me but I can't seem to find the answer please help! Mostly need help with parts 2, 3, 4. The IONOF (Integer On Number Of Factors) of an integer is the integer ...
0
votes
7answers
140 views

How to prove there doesn't exist $a,b \in \Bbb Z$ with $|a^2-5b^2|=2$ [on hold]

As it says in the headline, how does one prove that there doesn't exist $a, b$ $\in \Bbb Z$ with $|a^2-5b^2|=2$? Any hints?
1
vote
1answer
61 views

Integers tables $6\times6$ and $7\times7$

Can fill integers table $6\times 6$ so that the sum of all the numbers in each square $3\times3$ equal $2016$, and the sum of all the numbers in each square table $5\times5$ equal $2015$? ...
22
votes
2answers
12k views

Prove that two any consecutive terms of Fibonacci sequence are relatively prime

Prove that two any consecutive terms of Fibonacci sequence are relatively prime My attempt: We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 1$. Suppose that $\gcd(f_n, ...
3
votes
3answers
69 views

If $9 \mid 2^b-2^a$, then $7\mid2^b-2^a$

Prove that if $9 \mid 2^b-2^a$, then $7\mid2^b-2^a$. I am not sure how to prove this statement, but it seems that from $9 \mid 2^b-2^a$ we have $b-a = 6n$. Then what should I do from here to ...
2
votes
2answers
72 views

Show $x^2 + y^2 + 1 = 0 \pmod m$, iff $\,m \pmod 4 \ne 0$.

Show that $x^2 + y^2 + 1 = 0$ $\pmod m$ has solutions iff $\,m \pmod 4 \ne 0$. I know hot to show that this equation has solutions if m = p It's easy to show "$=>$", but I'm completery ...
2
votes
1answer
26 views

Looking for a simpler solution to a problem about the divisibility of combinatorial numbers

Here is the problem: For every positive integer r, there exists a natural number $n_r$ such that for every integer $n>n_r$, there is at least one $k$, where $1\leq k \leq n-1$,such that ...
0
votes
4answers
69 views

Is this recurrence relation $g_{n+1}=ig_n-g_{n-1}$ is a trivial?

Let $g_1=i$ and $g_2=-1$, where $i=\sqrt{-1}$, and $$g_{n+1}=ig_n-g_{n-1}$$ For $n=1,2,3,4, ...$ then $g_n:={i, -1, -2i, 3, 5i, -8, -13i, 21, ...}$ respectively. Is this recurrence relation is ...
6
votes
1answer
311 views

Elementary proof of prime number theorem?

From Wikipedia: "The prime number theorem is also equivalent to: $$lim_{x \rightarrow \infty} \frac{\psi(x)}{x}=1$$ where $$\psi(x) = \sum\limits_{n \leq x} \Lambda(n)$$ is the Chebyshev function. ...
1
vote
2answers
32 views

In $GF(q)$, are there the same number of quadratic residues as quadratic nonresidues?

I know that for $\mathbb Z_p^*$ (the multiplicative group of a field with $p$ elements where $p$ is a prime), there are $(p-1)/2$ quadratic residues, and thus $(p-1)/2$ quadratic nonresidues. We can ...
0
votes
1answer
47 views

Calculating the absolute value of sum of rational numbers [on hold]

If $\sqrt{9-8\cos40}=a+b\sec40$, and $a$ and $b$ are rational numbers, then $\lvert a+b\rvert =\,{}$?