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

learn more… | top users | synonyms (1)

7
votes
1answer
79 views

Is there always a prime between a prime and prime plus the index of that prime?

Is it known is there always a prime strictly between $p_n$ and $p_n+n$, where $p_n$ is the $n$-th prime number and $n\geq5$? I know about Bertrand`s postulate which states that for any integer $n>...
0
votes
1answer
21 views

Find maximum and minimum values for n digits in base d

Even if I know that with n digits the minimum value in base d is $d^{n-1}$ and the maximum is $d^{n}-1$, I would like to know ...
2
votes
4answers
86 views

Show that: $97|2^{48}-1$

Show that: $97|2^{48}-1$ My work: $$\begin{align} 2^{96}&\equiv{1}\pmod{97}\\ \implies (2^{48}-1)(2^{48}+1)&=97k\\ \implies (2^{24}-1)(2^{24}+1)(2^{48}+1) &=97k\\ \implies (2^{12}-1)(2^{...
3
votes
2answers
27 views

Solve the congruence system: $p \equiv 11\pmod{24}$ and $ p\equiv 3 \pmod 4$

I want to find the solutions of the congruences system: $p \equiv 11\pmod{24}$ and $ p\equiv 3 \pmod 4$. I probably have some mistake in my solution, can you tell me where I'm wrong? $ 4 $ and $...
2
votes
2answers
57 views

Show that :$89|2^{44}-1$

Show that :$89|2^{44}-1$ Using Fermat's theorem we have: $2^{88}\equiv{1}\pmod{89}\ \Rightarrow\ (2^{44}-1)(2^{44}+1)=89k$ , now how can be sure that: $89|2^{44}-1$??
0
votes
1answer
23 views

Let $F_n$ be a Fermat prime number prove that $\gamma_{F_n}(2)=2^{n+1}$

Let $F_n$ be a Fermat prime number. Prove that $\gamma_{F_n}(2)=2^{n+1}$. Here $\gamma_{F_n}(2)$ denotes the order of $2$ modulo $F_n$. My attempt: $F_0=2^{2^0}=2^{0+1} \quad\checkmark$ $F_1=5 \...
3
votes
1answer
61 views

Finding minimum difference between two linear functions

Given two functions of the form $y = m_1x + c_1$ and $y = m_2x + c_2$ where $m_1,m_2,c_1,c_2$ are positive integers. How to find the absolute minimum difference between the two functions for positive ...
4
votes
1answer
32 views

On primitive Pythagorean triplets with same greatest term

For the purpose of this question, I'll define a primitive Pythagorean triplet as a triplet of positive integers $(a, b, c)$ such that $a$ is odd; $b$ is even; $\gcd(a, b, c) = 1$; $a^2 + b^2 = c^2$. ...
4
votes
2answers
72 views

If $x$ and $y$ are positive numbers less than $20$ for which $x+y+xy=76$, what is $x+y$?

What is a simple way to solve this problem? I can do it by trying $x$ and $y$, starting from $1$. That does not look like the best way. If $x$ and $y$ are positive numbers less than $20$ for which ...
1
vote
1answer
32 views

Using parity to determine the answer for the given problem

Let $n$ be an integer greater than 0. The numbers $1, 2, 3, \ldots, n$ are written on a blackboard. We decide to erase from the blackboard any two numbers, and replace them with their nonnegative ...
0
votes
1answer
164 views

Minimum difference between two AP terms

Given two Arithmetic Progressions, A1=ax+b and A2=cy+d, that is we're given a, b ,c & d (where a, b, c, & d all are positive integers) how have to find minimum value of |A1-A2| by choosing x ...
1
vote
1answer
57 views

Method to find smallest value of $x$ in $x^2-x+C$ to receive non-primes

$\textit{Problem statement}$: Given the function $f(x)=x^2-x+C$, where $x$ is a positive integer $>1$ and $C$ is a positive integer ($C=0$ is also allowed), find some method and/or set of rules to ...
1
vote
4answers
42 views

$a\equiv{b}\pmod{m},a\equiv{b}\pmod{n}\ \Rightarrow\ a\equiv{b}\pmod{lcm(m,n)}$

Show that if $a\equiv{b}\pmod{m},a\equiv{b}\pmod{n}\ \Rightarrow\ a\equiv{b}\pmod{lcm(m,n)}$ I think this must be a basic theorem in number theory but couldn't find it in my books,also it's very ...
0
votes
1answer
28 views

Need a proof for a modular arithmetic property

From a book I knew something about RSA algorithm .There I found a modular arithmetic property i.e $ (a\bmod n)^d\mod n=a^d\bmod n$ I don't know why this property works .Can anyone give me an ...
21
votes
2answers
1k views

Is $\sqrt{n!}$ a natural number?

I'm new here (on Mathematics Stack Exchange). Also, I'm a 10th grade student not a math expert. So, my question is whether, $$\sqrt {n!} $$ comes in the set of the Natural Numbers. There were ...
0
votes
1answer
25 views

Compute the minimum value of $ \underline{A}\ \underline{B}\ \underline{C} - (A^2 + B^2 + C^2). $

Let $\underline{A}\ \underline{B}\ \underline{C}$ represent a three-digit base 10 number whose digits are $A$, $B$, and $C$ with $A \ge 1$. Compute the minimum value of $$ \underline{A}\ \underline{B}\...
0
votes
1answer
30 views

Computing difference in modular arithmetic. [closed]

Is there a meaningful kind of difference "$|a-b|$" in modular arithmetic? For example, in mod $12$, we would like to have $|0-11|= 1$ and $|0-1| = 1$.
2
votes
0answers
29 views

Division in modular arithmetic

Let $p$ be an odd prime. Given that $a\equiv b \pmod p$ and $c \equiv d \pmod p$, such that none of $a,b,c,d$ is a multiple of $p$. Under what conditions, $\frac{a}{c} \equiv \frac{b}{d} \pmod p$.
0
votes
0answers
10 views

Application of Reduced residue system and modular

What i have done is that : a)when p is 3k+1, the number of elements of S : 3k and b)when p is 3k+2, the number of elements of S : 3k+1, a)the number of elements of A is $3k$ because each one in ...
2
votes
3answers
57 views

$a^3+b^3+c^3\equiv{0}\pmod7\implies $ at least one of $a,b$ or $c$ is divisible by $7$

Show that if $a^3+b^3+c^3\equiv{0}\pmod7\implies$ at least one of $a,b$ or $c$ is divisible by $7$. Here it seems Fermat's theorem has no use. We could consider many different cases of remainders of ...
1
vote
3answers
28 views

solvability of congruence equation.

what i have done is that : 2,4,$p^k, 2p^k$ where p is odd prime, has primitive root. so let's suppose p is odd prime and primitive root of $p^s$ is g then $g^{{p^{s-1}(p-1)}/2} \equiv -1 \pmod {p^{s}} ...
4
votes
2answers
64 views

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$ According to Fermat's theorem: $$1^7+7^7+13^7+19^7+23^7\equiv{1+7+13+19+23}\pmod{7}\equiv{63}\pmod{7}\equiv{0}\pmod{7}$$ Now we need to show: $1^7+...
4
votes
2answers
58 views

If $n$ is prime, then $2^n+1$ is composite?

When $2^n-1$ is prime and $n>2$ then $n$ is prime. Then, when $2^n-1$ is prime, why $2^n+1$ is composite? What I have done is this. Let's suppose $2^n+1$ is prime, then it will be contradiction. ...
1
vote
4answers
50 views

Show that if $\ 7|5a-2$ then $\ 49|a^2-5a-6\ $

Show that if $\ 7|5a-2$ then $\ 49|a^2-5a-6\ $ , ($\ a$ is positive integer) My work: $7|5a-2 \Rightarrow\ 49|35a-14a,49a^2 \Rightarrow\ 49|14a^2+14 \Rightarrow\ 42a^2+42a,49a^2+49a\ \Rightarrow\ ...
-1
votes
0answers
20 views

Equivalence giving prime / pseudoprime / Carmichael

Prove that, if $a^a \equiv (a+1)/x \pmod{a+x}$, where $a$ and $x$ are coprime then $a+x$ is either a prime, base $x$ pseudoprime, or a Carmichael number. How is it related to the fact that $(a+x)^{a+...
0
votes
1answer
26 views

Intersection and complement of $\{3^k \mid k \in \Bbb N\}$ and $\{l^3 \mid l \in \Bbb N\}$

Let A = $\{3^k \mid k \in \Bbb N\},\ C = \{l^3 \mid l \in \Bbb N\}$. a) Determine $A − C$. b) Determine $A \cap C$. Approach: if $l=3^k$ then $l^3=3^{3k}$ but we know that $2k \in N$, so ...
-1
votes
1answer
406 views

Kth number whose all digits are even [closed]

As my title says.. what is the formula for kth number whose all digits are even (i.e digits can take 0,2,4,6,8)?
0
votes
0answers
23 views

Adjusted rational approximation of reals?

The rational numbers are dense in the real numbers, which means that $\forall r \in \mathbb{R}, \forall \varepsilon > 0, \exists \frac{q}{p} \in \mathbb{Q}: | r - \frac{q}{p} | < \varepsilon$. ...
3
votes
5answers
89 views

How can I find the last digit of $17^{68}$ and the last both digits of $14^{200}$?

I have to compute the last digit of $17^{68}$ and the last both digits of $14^{200}$. For the first exercise, I get $$17^4=...1 \Rightarrow 17^{68}=(17^4)^{17} = (...1)^{17}=\ .... 1.$$ For the ...
3
votes
2answers
98 views

If $n$ is a power of $13$, does $n \mid 5^n + 8^n$?

Motivated by this question: Is it true that if $n$ is a power of $13$, then $n \mid 5^n + 8^n$ ? The limited data in oeis/A045597 seems to suggest it is true. The converse does not hold. The ...
0
votes
1answer
20 views

Congruences and Legendre

I am trying to solve a Legendre symbol problem and have got it down to the following: When $p \equiv 1\mod4$ and a prime such that $p \neq 2,7$, $\left(\frac{7}{p}\right) = \left(\frac{p}{7}\right)...
3
votes
1answer
69 views

Is there a Fermat-era proof of Theorem 69 from Dickson's Intro to NT?

In Dickson’s Introduction to the Theory of Numbers (Ch. VI, pp. 91-93), he gives the following [wonderful and wonderfully general] theorem. Theorem 69: All integral solutions of $$x^2-my^2=zw$$ ...
0
votes
0answers
39 views

Why does $p \equiv 1,2,4 \pmod 7 \iff p \equiv 1,9,25 \pmod {28}$ where $p \equiv 1 \pmod 4$

Why does $p \equiv 1,2,4 \pmod 7 \iff p \equiv 1,9,25 \pmod {28}$ I can find primes and probably work this out but is there a quicker way? Edit: p is an odd prime and $p \equiv 1 \pmod 4$
1
vote
4answers
64 views

Prove using induction on n that: $8\mid5^n+2(3^{n-1})+1$

How can we use induction to prove that $8\mid5^n+2(3^{n-1})+1$ for any natural $n$?
2
votes
3answers
34 views

Proof about least prime numbers dividing n

Assume $n \in N$ is composite. Prove if p is the least prime number dividing n, then $p^2 \leq n$ Approach: I tried to write the first few prime and composite numbers but I didn't any patter. Any ...
3
votes
4answers
46 views

Prove that if $a$ and $b$ are positive integers satisfying $\gcd(a,b)=\operatorname{lcm}(a,b)$,then $a=b$

Prove that if $a$ and $b$ are positive integers satisfying $\gcd(a,b)=\operatorname{lcm}(a,b)$,then $a=b$. Since the formula for two positive integers $a,b$ is $\operatorname{lcm}(a,b)=\frac{ab}{\...
-2
votes
2answers
80 views

Prove or disprove $x^2-x$ is divisible by $x$ [closed]

Can someone prove or disprove this statement: Given a positive integer $x>1$, is it true that $x^2-x$ gives a number that is divisible by $x$?
1
vote
1answer
24 views

Existence of prime which makes Legendre symbol -1

Let $a$ be a positive integer which is not a square, i.e. $a\neq n^2$ for all $n=1,2,3,\ldots$. Show that there exists an odd prime $p$ such that $\left(\frac{a}{p}\right)=-1.$ Hint: ...
1
vote
1answer
45 views

What are numbers? Literally, how can we know what a number is? [closed]

I've been driving myself to the point of insanity trying to figure out exactly what numbers are, so much so that I've enrolled in philosophy logic classes just to try and find answers -- I'm very ...
0
votes
2answers
23 views

Proving an operation $*$ is associative.

We are given that $*$ is an operation on a two-element set $\{e,a\}$ and that $e$ is an identity element for $*$. We want to prove that $*$ is associative. We know $a*e = e*a$ because $e$ is an ...
12
votes
1answer
91 views

Permutations of the set $\{1,2,…,n\}$ and prime numbers

I just observed for some small $n$ that we can find a permutation of the set $\{1,2,...,n\}$ which is such that sum of any two adjacent numbers is a prime number. Take for example set $\{1,2,3,4,5,6\}...
1
vote
2answers
115 views

Prove that if $n|5^n + 8^n$, then $13|n$ using induction

I have to prove using mathematical induction that if $n \ge 2$ and $n|5^n + 8^n$, then $13|n$. Please help me.
1
vote
4answers
103 views

Proof that $3^n | 2^{3^n} + 1$

Question: Proof by induction that $3^n | 2^{3^n} + 1$. Attempt: $$ 2^{3^{n+1}} + 1 = 2^{3^n} 2^3 + 1 = 2^{3^n} 2^3 + 1 + 2^3 - 2^3 = 2^3( 2^{3^n} + 1 ) + 1 -2^3$$ And the first is $3^n |$ ...
3
votes
1answer
50 views

Show that the equation $x^2+y^2+z^2=x^2y^2$ has no integer solution,except $x=y=z=0$

Show that the equation $x^2+y^2+z^2=x^2y^2$ has no integer solution,except $x=y=z=0.$ Let one of the $x,y,z$ be even number.Let $x=2p$ $x^2+y^2+z^2=x^2y^2$ This gives $y^2+z^2$ is also even,which ...
0
votes
3answers
47 views

Find the value of $a$ if $x^2+y^2=axy$ has positive integer solution.

Find the value of $a$ if $x^2+y^2=axy$ has positive integer solution. My try: Let g.c.d of $x$ and $y$ is $d$ i.e.$(x,y)=d$ and let $x=dx',y=dy'.$ Then $x'^2+y'^2=ax'y'$ I am stuck here.The answer ...
2
votes
1answer
37 views

Finding all triplets of positive integers with certain property

Fix a $k \in \mathbb{N}$ How do I find all sets of positive integers $a_{1},a_{2},...,a_{k}$ such that the sum of any triplet is divisible by each member of the triplet. I couldn't see ...
1
vote
5answers
151 views

Solve $ord_x(2) = 20$

Given that the (multiplicative) order of $2$ mod $x$ is $20$, how can I work out what $x$ is?
0
votes
2answers
47 views

Possible mis-interpretation in Project Euler #21

Here is the problem statement for Problem 21 of Project Euler. Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$). If $d(a) = b$ ...
0
votes
3answers
45 views

Modular Arithmetic: Computing last digit of $206746^{20}$ [duplicate]

I have been given the number: ${206746}^{20 }$and the problem wants me to compute the last digit using modular arithmetic. How would I go about this? I know that since the ones digit is 6, no matter ...
1
vote
3answers
39 views

The number of divisors

I am reading a math book. It states the following rule: For an integer $n$ greater than 1, let the prime factorization of $n$ be $$n=p^a_1p^b_2p^c_3...p^m_k$$ Here $a, b, c,..., m$ are ...