Lloyd: Ted's point about the sovereignty of the tribes is critical, and a major issue in AZ

Arizona has 21 Indian tribes, which hold about a quarter of the land in the state. The Navajo Nation makes it illegal to carry a deadly weapon including a gun.
The Tohono O’odham Nation prohibits the carry of a concealed weapon on a person or in a vehicle.

If traveling on a Federal or State highway, you are not technically on tribal land. Back roads are different.

I found a link to the Crow Reservation laws, but you'll have to navigate to Chapter 8; Weapons
https://narf.org/nill/codes/crow_montana/index.html

Don't take someone's word; do your homework before going.