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

learn more… | top users | synonyms (1)

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
63 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
47 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
405 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
96 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
61 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
44 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
90 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
114 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
36 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
150 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 ...
3
votes
2answers
54 views

How do I quickly find if a big number $\bmod n$ is odd or even?

How do I quickly find if big number is even or odd? For example I want to find if $17^{50}\mod 101$ even or odd ?
0
votes
2answers
60 views

If $b^2 \equiv 1 \pmod 3$, is it possible to have $\sigma(b^2) \equiv b^2 \pmod 3$?

The title says it all. Let $\sigma(N)$ denote the sum of the divisors of the positive integer $N$. To paraphrase my question: If $3 \mid \left(b^2 - 1\right)$, is it possible to have $3 \mid \...
1
vote
1answer
38 views

Nice shapes of ideals of $\mathbb{Z}[i]$ from a (lattice) geometric point of view?

If we draw the lattice for the ideal generated by $(2+i)$ in $\mathbb{Z}[i]$, and look at what is happening modulo $(2+i)$, we see a beautiful square, although it is rotated a little bit counterclock-...
7
votes
7answers
175 views

Most students asked why is that ${a\over b}\div{c\over d}={ad\over bc}$

Most students asked why is that $${a\over b}\div{c\over d}={ad\over bc}$$ I just told them: inverse the second fraction and multiply. Why? They ask me. I have no idea. Any logical answers to them ...
2
votes
1answer
31 views

A question on the greatest common divisor of integers and their divisor sum

Suppose that $x, y, z$ are positive integers. Let $\sigma(x)$ be the sum of the divisors of $x$, and let $\gcd(y, z)$ be the greatest common divisor of $y$ and $z$. Here is my question: If the ...
9
votes
5answers
143 views

Prove that $2^n$ does not divide $n!$

I want to prove that $2^n$ does not divide $n!$. I was trying by induction and I'm confused about if what I'm doing is right. First I test it with $n=1$. In fact: $$2^1 \nmid 1!$$ So if i take the ...
2
votes
5answers
68 views

Let $n \in \mathbb{N}$. Proving that $13$ divides $(4^{2n+1} + 3^{n+2})$

Let $n \in \mathbb{N}$. Prove that $13 \mid (4^{2n+1} + 3^{n+2} ). $ Attempt: I wanted to show that $(4^{2n+1} + 3^{n+2} ) \mod 13 = 0. $ For the first term, I have $4^{2n+1} \mod 13 = (4^{2n} \cdot ...
0
votes
1answer
28 views

How to get values of Summatory Liouville function from Mertens function?

All: For Liouville function λ(n), we can define summatory Liouville as the accumulated sum of of λ(n). Mertens function is the accumulated sum of Mobius function. Is there any ways to get the value ...
1
vote
1answer
21 views

Strong Pseudoprime to base square?

Question: Let n>1 be an odd composite integer and let a be an integer with (a,n)=1. Show that, if n is a strong pseudoprime to base a, then n is also a strong pseudoprime to base $a^2$ What ...
1
vote
1answer
19 views

Can $\sigma(2^r)$ be abundant for $r > 1$?

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(y) < 2y$, $y$ is called deficient; if $\sigma(z) > 2z$, $z$ is called abundant. Questions (1) Can $\...
1
vote
0answers
48 views

Euclidean algorithm: THE GAME OF EUCLID

In his book "Elementary Number Theory:A Problem Solving Approach" (Euclidean algorithm/Derived Sets/ first chapter page:17,19) Joe Roberts describes a number: $$\tau=\frac{1+\sqrt{5}}{2}$$ further he ...
2
votes
1answer
63 views

Fifth last digit of a huge number

How can I find the fifth last digit of $5^{5^{5^{5^5}}}$? I tried to evaluate $5^{5^{5^{5^5}}}\pmod {100000}$. But the exponent is so huge that I'm unable to evaluate it. Also, $(5,100000)=5$ , so $5$ ...
1
vote
2answers
73 views

If $a \in A$ and $b \in B$ then $2a \in B$ and $2b \in A$ and $(a+b)^{2014}\in C$ [closed]

Below are questions that it think I know how to do but im not $100\%$ sure. $(i)$ asks if $a$ is odd so $a=k+1$, then prove $2a$ is even so $2a = 2k+2.$ The second and third differ a little am I ...
3
votes
2answers
31 views

A congruence mod p

Let $p$ be a prime number. Show that $$2^2\times 4^2\times \cdots \times (p-1)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod {p} .$$ Any help will be appreciated!
1
vote
1answer
30 views

Write a number as different differences of powers

Is there a positive integer $n$ that can be written as $a_i-b_i$ for $i=2,3,4,5$, where $a_i,b_i$ are positive perfect $i$th powers, and no two among $a_i$ or $b_i$ are the same? This might be ...
0
votes
0answers
14 views

Value of Phi(y^n)

Prove that the Multiplicative order $m$ of: $m(-1, 2^n)/(\phi $$2^n$) = $$1/2^{n-2}$$ and $m(-1, 3^n)/(\phi $$3^n$) = $$1/3^{n-1}$$ and for no other positive integer $y > 3$: $m(-1, y^n)/(\...
1
vote
1answer
21 views

is there an odd prime p such that (n/p)=1?

For any positive integer n, is there exists an odd prime p such that $(\dfrac{n}{p}) = 1$? i think that it will be true.. but i don't know what is right. what i have done is that .. when n is even, ...
0
votes
2answers
46 views

Consider ($6-a)(6-b)(6-c)(6-d)(6-e)$ are $5$ distinct factors of $45.$ find value of $a+b+c+d+e$ [closed]

Consider $(6-a)(6-b)(6-c)(6-d)(6-e)$ are $5$ distinct factors of $45.$ Find the value of $a+b+c+d+e$.
1
vote
1answer
15 views

Repeating period in binary conversion

A common algorithm for converting a decimal number that is between 0 and 1 (Ex: 0.1) to binary is to multiply by 2 and record the integer part of the result. Then, you subtract that integer from the ...
2
votes
0answers
36 views

Integers of the form $m^k-n^k$ [closed]

We know that an integer number is the difference of two squares if and only if it is not congruent to 2 mod 4. As a generalization, do we have a similar statement for integers of the form $m^k-n^k$, ...